

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Cone Programming &mdash; CVXOPT User&#39;s Guide</title>
  

  
  
  
  

  
  <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
        <script src="_static/jquery.js"></script>
        <script src="_static/underscore.js"></script>
        <script src="_static/doctools.js"></script>
        <script src="_static/language_data.js"></script>
    
    <script type="text/javascript" src="_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="copyright" title="Copyright" href="copyright.html" />
    <link rel="next" title="Nonlinear Convex Optimization" href="solvers.html" />
    <link rel="prev" title="Sparse Linear Equations" href="spsolvers.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="index.html" class="icon icon-home"> CVXOPT User's Guide
          

          
          </a>

          
            
            
              <div class="version">
                1.2.5
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <ul class="current">
<li class="toctree-l1"><a class="reference internal" href="copyright.html">Copyright and License</a></li>
<li class="toctree-l1"><a class="reference internal" href="intro.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="matrices.html">Dense and Sparse Matrices</a></li>
<li class="toctree-l1"><a class="reference internal" href="blas.html">The BLAS Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="lapack.html">The LAPACK Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="fftw.html">Discrete Transforms</a></li>
<li class="toctree-l1"><a class="reference internal" href="spsolvers.html">Sparse Linear Equations</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Cone Programming</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#linear-cone-programs">Linear Cone Programs</a></li>
<li class="toctree-l2"><a class="reference internal" href="#quadratic-cone-programs">Quadratic Cone Programs</a></li>
<li class="toctree-l2"><a class="reference internal" href="#linear-programming">Linear Programming</a></li>
<li class="toctree-l2"><a class="reference internal" href="#quadratic-programming">Quadratic Programming</a></li>
<li class="toctree-l2"><a class="reference internal" href="#second-order-cone-programming">Second-Order Cone Programming</a></li>
<li class="toctree-l2"><a class="reference internal" href="#semidefinite-programming">Semidefinite Programming</a></li>
<li class="toctree-l2"><a class="reference internal" href="#exploiting-structure">Exploiting Structure</a></li>
<li class="toctree-l2"><a class="reference internal" href="#optional-solvers">Optional Solvers</a></li>
<li class="toctree-l2"><a class="reference internal" href="#algorithm-parameters">Algorithm Parameters</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="solvers.html">Nonlinear Convex Optimization</a></li>
<li class="toctree-l1"><a class="reference internal" href="modeling.html">Modeling</a></li>
<li class="toctree-l1"><a class="reference internal" href="c-api.html">C API</a></li>
<li class="toctree-l1"><a class="reference internal" href="printing.html">Matrix Formatting</a></li>
<li class="toctree-l1"><a class="reference external" href="http://cvxopt.org">cvxopt.org</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="index.html">CVXOPT User's Guide</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="index.html">Docs</a> &raquo;</li>
        
      <li>Cone Programming</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="cone-programming">
<span id="c-coneprog"></span><h1>Cone Programming<a class="headerlink" href="#cone-programming" title="Permalink to this headline">¶</a></h1>
<p>In this chapter we consider convex optimization problems of the form</p>
<div class="math">
<p><img src="_images/math/bcfcc32ea50d37180cedf362db80a4901cbc05bd.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; (1/2) x^TPx + q^T x \\
\mbox{subject to} &amp; G x \preceq h \\
                  &amp; Ax = b.
\end{array}"/></p>
</div><p>The linear inequality is a generalized inequality with respect to a
proper convex cone.  It may include componentwise vector inequalities,
second-order cone inequalities, and linear matrix inequalities.</p>
<p>The main solvers are <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a>, described in the
sections <a class="reference internal" href="#s-conelp"><span class="std std-ref">Linear Cone Programs</span></a> and <a class="reference internal" href="#s-coneqp"><span class="std std-ref">Quadratic Cone Programs</span></a>.  The function
<code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code> is restricted to problems with linear cost functions, and
can detect primal and dual infeasibility.  The function <code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code>
solves the general quadratic problem, but requires the problem to be
strictly primal and dual feasible.  For convenience (and backward
compatibility), simpler interfaces to these function are also provided
that handle pure linear programs, quadratic programs, second-order cone
programs, and semidefinite programs.  These are described in the sections
<a class="reference internal" href="#s-lpsolver"><span class="std std-ref">Linear Programming</span></a>, <a class="reference internal" href="#s-qp"><span class="std std-ref">Quadratic Programming</span></a>, <a class="reference internal" href="#s-socpsolver"><span class="std std-ref">Second-Order Cone Programming</span></a>, <a class="reference internal" href="#s-sdpsolver"><span class="std std-ref">Semidefinite Programming</span></a>.
In the section <a class="reference internal" href="#s-conelp-struct"><span class="std std-ref">Exploiting Structure</span></a> we explain how custom solvers can
be implemented that exploit structure in cone programs.  The last two
sections describe optional interfaces to external solvers, and the
algorithm parameters that control the cone programming solvers.</p>
<div class="section" id="linear-cone-programs">
<span id="s-conelp"></span><h2>Linear Cone Programs<a class="headerlink" href="#linear-cone-programs" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.solvers.conelp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">conelp</code><span class="sig-paren">(</span><em class="sig-param">c</em>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">primalstart</em><span class="optional">[</span>, <em class="sig-param">dualstart</em><span class="optional">[</span>, <em class="sig-param">kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.conelp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a pair of primal and dual cone programs</p>
<div class="math">
<p><img src="_images/math/9f18ba54fa478c728e3a3536166f874c17aa7c04.png" alt="\begin{array}[t]{ll}
\mbox{minimize}   &amp; c^T x \\
\mbox{subject to} &amp; G x + s = h \\
                  &amp; Ax = b \\
                  &amp; s \succeq 0
\end{array}
\qquad\qquad
\begin{array}[t]{ll}
\mbox{maximize}   &amp; -h^T z - b^T y \\
\mbox{subject to} &amp; G^T z + A^T y + c = 0 \\
                  &amp; z \succeq 0.
\end{array}"/></p>
</div><p>The primal variables are <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and <img class="math" src="_images/math/106b04b320e75010b1d8029e59244f234f75e6f9.png" alt="s"/>.  The dual variables
are <img class="math" src="_images/math/1b5e577d6216dca3af7d87aa122a0b9b360d6cb3.png" alt="y"/>, <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>.  The inequalities are interpreted as
<img class="math" src="_images/math/4ac9a8351b68de952fda2e33246216aa5edb2818.png" alt="s \in C"/>, <img class="math" src="_images/math/6981ec4aaaf7392f4bf828ef63be506799574e5e.png" alt="z\in C"/>, where <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> is a cone defined as
a Cartesian product of a nonnegative orthant, a number of second-order
cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/03cfea18434ec87caa164206e463d7a230e1cb5c.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
    \cdots \times C_{M+N}"/></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/d767754db8d214ccf0dcaf05b48317d378fbddb5.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
    C_0 &amp; =
        \{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\}, \\
    C_{k+1} &amp; = \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1}
        \; | \; u_0 \geq \|u_1\|_2 \},  \quad k=0,\ldots, M-1, \\
    C_{k+M+1} &amp;= \left\{ \svec(u) \; | \; u \in \symm^{t_k}_+
        \right\}, \quad k=0,\ldots,N-1.
\end{split}"/></p>
</div><p>In this definition, <img class="math" src="_images/math/5866199ac7f27f9fa8f345c8d6bd6f14fc869908.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix
<img class="math" src="_images/math/9b444cf6329a14140aee8ff5a06ff30772cc1c2f.png" alt="u"/> stored as a vector in column major order.  The structure of
<img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> is specified by <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  This argument is a dictionary with
three fields.</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">dims['l']</span></code>:</dt><dd><p><img class="math" src="_images/math/470aa65888a2971c9346e573f12b37ea406b8ec9.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['q']</span></code>:</dt><dd><p><img class="math" src="_images/math/79b3736681052735beb52087fe8a1b6c188338fb.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['s']</span></code>:</dt><dd><p><img class="math" src="_images/math/d706fc3d557d35b283be36ac9e240324b68b34b9.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</p>
</dd>
</dl>
<p>The default value of <code class="docutils literal notranslate"><span class="pre">dims</span></code> is
<code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></code>,
i.e., by default the
inequality is interpreted as a componentwise vector inequality.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">c</span></code>, <code class="docutils literal notranslate"><span class="pre">h</span></code>, and <code class="docutils literal notranslate"><span class="pre">b</span></code> are real single-column dense
matrices.  <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are real dense or sparse matrices.  The
number of rows of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> is equal to</p>
<div class="math">
<p><img src="_images/math/95c7fad2a12f832a0675a00c80c4a8894297d2b8.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2."/></p>
</div><p>The columns of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> are vectors in</p>
<div class="math">
<p><img src="_images/math/1e0371cc3025278f588fd7d0ccfcc2510ff2f8cf.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2}  \times \cdots \times
\reals^{t_{N-1}^2},"/></p>
</div><p>where the last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> components represent symmetric matrices
stored in column major order.  The strictly upper triangular entries
of these matrices are not accessed (i.e.,  the symmetric matrices are
stored in the <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code>-type column major order used in the
<code class="xref py py-mod docutils literal notranslate"><span class="pre">blas</span></code> and <code class="xref py py-mod docutils literal notranslate"><span class="pre">lapack</span></code> modules).  The default values for <code class="docutils literal notranslate"><span class="pre">A</span></code>
and <code class="docutils literal notranslate"><span class="pre">b</span></code> are matrices with zero rows, meaning that there are no
equality constraints.</p>
<p><code class="docutils literal notranslate"><span class="pre">primalstart</span></code> is a dictionary with keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, used as an optional primal starting point.
<code class="docutils literal notranslate"><span class="pre">primalstart['x']</span></code> and <code class="docutils literal notranslate"><span class="pre">primalstart['s']</span></code> are real dense
matrices of size (<img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/>, 1) and (<img class="math" src="_images/math/52ddc0cde6d632f631533173562fe3ca375b1f32.png" alt="K"/>, 1), respectively,
where <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> is the length of <code class="docutils literal notranslate"><span class="pre">c</span></code>.  The vector
<code class="docutils literal notranslate"><span class="pre">primalstart['s']</span></code> must be strictly positive with respect
to the cone <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/>.</p>
<p><code class="docutils literal notranslate"><span class="pre">dualstart</span></code> is a dictionary with keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code>,
used as an optional dual starting point.  <code class="docutils literal notranslate"><span class="pre">dualstart['y']</span></code> and
<code class="docutils literal notranslate"><span class="pre">dualstart['z']</span></code> are real dense matrices of size (<img class="math" src="_images/math/141bbefb74014fc5e43499901bf78607ae335583.png" alt="p"/>, 1)
and (<img class="math" src="_images/math/52ddc0cde6d632f631533173562fe3ca375b1f32.png" alt="K"/>, 1), respectively, where <img class="math" src="_images/math/141bbefb74014fc5e43499901bf78607ae335583.png" alt="p"/> is the number of
rows in <code class="docutils literal notranslate"><span class="pre">A</span></code>.  The vector <code class="docutils literal notranslate"><span class="pre">dualstart['s']</span></code> must be strictly
positive with respect to the cone <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/>.</p>
<p>The role of the optional argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> is explained in
the section <a class="reference internal" href="#s-conelp-struct"><span class="std std-ref">Exploiting Structure</span></a>.</p>
<p><a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> returns a dictionary that contains the result and
information about the accuracy of the solution.  The most important
fields have keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code>.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> field  is a string
with possible values <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code>.  The meaning of
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> fields
depends on the value of <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>.</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code></dt><dd><p>In this case the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries contain the primal and dual solutions, which
approximately satisfy</p>
<div class="math">
<p><img src="_images/math/957b97bc1591647fef3ac407dd3dd3e99c37fcd5.png" alt="Gx + s = h, \qquad Ax = b, \qquad G^T z  + A^T y + c = 0,

s \succeq 0, \qquad z \succeq 0, \qquad  s^T z = 0."/></p>
</div><p>The other entries in the output dictionary summarize the accuracy
with which these optimality conditions are satisfied.  The fields
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">objective'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">objective'</span></code>, and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'gap'</span></code> give the primal objective <img class="math" src="_images/math/db7426d70cdd8a4c33c3f1b8f7bdc9ba1b62c43a.png" alt="c^Tx"/>, dual
objective <img class="math" src="_images/math/8ba9d3d0710a882764a58249d7a443b475a5b7d8.png" alt="-h^Tz - b^Ty"/>, and the gap <img class="math" src="_images/math/bca8217ac2efcad7312d6e496b4e4c82d8d179f6.png" alt="s^Tz"/>.  The
field <code class="xref py py-const docutils literal notranslate"><span class="pre">'relative</span> <span class="pre">gap'</span></code> is the relative gap, defined as</p>
<div class="math">
<p><img src="_images/math/056427854bd8d5a1fa428fff460d45b749aebc2a.png" alt="\frac{ s^Tz }{ \max\{ -c^Tx, -h^Tz-b^Ty \} }
\quad \mbox{if} \quad \max\{ -c^Tx, -h^Tz-b^Ty \} &gt; 0"/></p>
</div><p>and <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> otherwise.  The fields
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></code>
are the residuals in the primal and dual equality constraints,
defined as</p>
<div class="math">
<p><img src="_images/math/fcc17fd59806862a629796f0d7f0e8f43778e7bd.png" alt="\max\{ \frac{ \|Gx+s-h\|_2 }{ \max\{1, \|h\|_2\} },
    \frac{ \|Ax-b\|_2 }{ \max\{1,\|b\|_2\} } \}, \qquad
\frac{ \|G^Tz + A^Ty + c\|_2 }{ \max\{1, \|c\|_2\} },"/></p>
</div><p>respectively.</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code></dt><dd><p>The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code> entries are <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, and
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries provide an approximate
certificate of infeasibility, i.e., vectors that approximately
satisfy</p>
<div class="math">
<p><img src="_images/math/482017ed70f2f392091ce55bf925c4d264ca15ba.png" alt="G^T z + A^T y = 0, \qquad h^T z + b^T y = -1, \qquad
z \succeq 0."/></p>
</div><p>The field <code class="xref py py-const docutils literal notranslate"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">primal</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></code>
gives the residual</p>
<div class="math">
<p><img src="_images/math/8d53a80f87a15ba0d310801a0af822da73c3fcaf.png" alt="\frac{ \|G^Tz + A^Ty\|_2 }{ \max\{1, \|c\|_2\} }."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code></dt><dd><p>The <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries are <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, and
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code> entries contain an approximate
certificate of dual infeasibility</p>
<div class="math">
<p><img src="_images/math/3f1dd94c34f67811ddb2df9812cfb065dea10aac.png" alt="Gx + s = 0, \qquad Ax=0, \qquad  c^T x = -1, \qquad
s \succeq 0."/></p>
</div><p>The field <code class="xref py py-const docutils literal notranslate"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">dual</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></code>
gives the residual</p>
<div class="math">
<p><img src="_images/math/ad2c8101af3f233ceefa1ec6865721f302b84cfd.png" alt="\max\{ \frac{ \|Gx + s\|_2 }{ \max\{1, \|h\|_2\} },
\frac{ \|Ax\|_2 }{ \max\{1, \|b\|_2\} } \}."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code></dt><dd><p>This indicates that the algorithm terminated early due to
numerical difficulties or because the maximum number of iterations
was reached.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries contain the iterates when the algorithm
terminated.  Whether these entries are useful, as approximate
solutions or certificates of primal and dual infeasibility, can be
determined from the other fields in the dictionary.</p>
<p>The fields <code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">objective'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">objective'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'gap'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'relative</span> <span class="pre">gap'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></code> are defined as when <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>
is <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code>.  The field
<code class="xref py py-const docutils literal notranslate"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">primal</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></code> is defined
as</p>
<div class="math">
<p><img src="_images/math/c34401e75e80cc822827c5d5175de08a5bbffced.png" alt="\frac{ \|G^Tz+A^Ty\|_2 }{ -(h^Tz + b^Ty) \max\{1, \|h\|_2 \} }."/></p>
</div><p>if <img class="math" src="_images/math/da8dad38c611fbd068672223f3f152e89ee7477e.png" alt="h^Tz+b^Ty &lt; 0"/>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> otherwise.  A small
value of this residual indicates that <img class="math" src="_images/math/1b5e577d6216dca3af7d87aa122a0b9b360d6cb3.png" alt="y"/> and <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>,
divided by <img class="math" src="_images/math/700c6a7cc89a7142ae312c5cb4f1f5b78da350dd.png" alt="-h^Tz-b^Ty"/>, are an approximate proof of primal
infeasibility.  The field
<code class="xref py py-const docutils literal notranslate"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">dual</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></code> is defined as</p>
<div class="math">
<p><img src="_images/math/0bf595687ae571b0147a101f606500879246b152.png" alt="\max\{ \frac{ \|Gx+s\|_2 }{ -c^Tx \max\{ 1, \|h\|_2 \} },
\frac{ \|Ax\|_2 }{ -c^Tx \max\{1,\|b\|_2\} }\}"/></p>
</div><p>if <img class="math" src="_images/math/04342bcceed278806ffa3c6deee7f762c50a6eab.png" alt="c^Tx &lt; 0"/>, and as <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> otherwise.  A small value
indicates that <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and <img class="math" src="_images/math/106b04b320e75010b1d8029e59244f234f75e6f9.png" alt="s"/>, divided by <img class="math" src="_images/math/e00cdcd92f7a9d17060f49d50fad98569a249cd0.png" alt="-c^Tx"/>
are an approximate proof of dual infeasibility.</p>
</dd>
</dl>
<p>It is required that</p>
<div class="math">
<p><img src="_images/math/8655418fcbc61747ed3bd70aa2d1ecc1db06a5c9.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank(\left[\begin{array}{c} G \\ A \end{array}\right]) = n,"/></p>
</div><p>where <img class="math" src="_images/math/141bbefb74014fc5e43499901bf78607ae335583.png" alt="p"/> is the number or rows of <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/> and <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> is
the number of columns of <img class="math" src="_images/math/89878909dbb648acdc4a44ded1bd982d7bddef5d.png" alt="G"/> and <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/>.</p>
</dd></dl>

<p>As an example we solve the problem</p>
<div class="math">
<p><img src="_images/math/a5d23ddad04b332c54e468fd62d6493589d61339.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp;  -6x_1 - 4x_2 - 5x_3 \\*[1ex]
\mbox{subject to}
    &amp; 16x_1 - 14x_2 + 5x_3 \leq -3 \\*[1ex]
    &amp; 7x_1 + 2x_2 \leq 5 \\*[1ex]
    &amp; \left\| \left[ \begin{array}{c}
         8x_1 + 13x_2 - 12x_3 - 2  \\
        -8x_1 + 18x_2 +  6x_3 - 14 \\
          x_1 -  3x_2 - 17x_3 - 13 \end{array}\right] \right\|_2
        \leq -24x_1 - 7x_2 + 15x_3 + 12 \\*[3ex]
    &amp; \left\| \left[
      \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array}
      \right] \right\|_2 \leq 10 \\*[3ex]
    &amp; \left[\begin{array}{ccc}
       7x_1 +  3x_2 + 9x_3 &amp; -5x_1 + 13x_2 + 6x_3 &amp;
           x_1 - 6x_2 - 6x_3\\
      -5x_1 + 13x_2 + 6x_3 &amp;   x_1 + 12x_2 - 7x_3 &amp;
          -7x_1 -10x_2 - 7x_3\\
       x_1 - 6x_2 -6x_3 &amp; -7x_1 -10x_2 -7 x_3 &amp;
          -4x_1 -28 x_2 -11x_3
       \end{array}\right]
\preceq \left[\begin{array}{ccc}
    68  &amp; -30 &amp; -19 \\
   -30 &amp; 99  &amp;  23 \\
   -19 &amp; 23  &amp; 10 \end{array}\right].
\end{array}"/></p>
</div><div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">4.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">16.</span><span class="p">,</span> <span class="mf">7.</span><span class="p">,</span>  <span class="mf">24.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">8.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>
<span class="go">                   7.,  -5.,   1.,  -5.,   1.,  -7.,   1.,   -7.,  -4.],</span>
<span class="go">                [-14., 2.,   7., -13., -18.,   3.,  0.,  0., -1.,  0.,</span>
<span class="go">                   3.,  13.,  -6.,  13.,  12., -10.,  -6.,  -10., -28.],</span>
<span class="go">                [  5., 0., -15.,  12.,  -6.,  17.,  0.,  0.,  0., -1.,</span>
<span class="go">                   9.,   6.,  -6.,   6.,  -7.,  -7.,  -6.,   -7., -11.]])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">,</span>  <span class="mf">12.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">14.</span><span class="p">,</span> <span class="o">-</span><span class="mf">13.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>
<span class="go">                  68., -30., -19., -30.,  99.,  23., -19.,   23.,  10.] )</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span> <span class="p">[</span><span class="mi">3</span><span class="p">]}</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;status&#39;</span><span class="p">]</span>
<span class="go">&#39;optimal&#39;</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">])</span>
<span class="go">[-1.22e+00]</span>
<span class="go">[ 9.66e-02]</span>
<span class="go">[ 3.58e+00]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;z&#39;</span><span class="p">])</span>
<span class="go">[ 9.30e-02]</span>
<span class="go">[ 2.04e-08]</span>
<span class="go">[ 2.35e-01]</span>
<span class="go">[ 1.33e-01]</span>
<span class="go">[-4.74e-02]</span>
<span class="go">[ 1.88e-01]</span>
<span class="go">[ 2.79e-08]</span>
<span class="go">[ 1.85e-09]</span>
<span class="go">[-6.32e-10]</span>
<span class="go">[-7.59e-09]</span>
<span class="go">[ 1.26e-01]</span>
<span class="go">[ 8.78e-02]</span>
<span class="go">[-8.67e-02]</span>
<span class="go">[ 8.78e-02]</span>
<span class="go">[ 6.13e-02]</span>
<span class="go">[-6.06e-02]</span>
<span class="go">[-8.67e-02]</span>
<span class="go">[-6.06e-02]</span>
<span class="go">[ 5.98e-02]</span>
</pre></div>
</div>
<p>Only the entries of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> defining the lower triangular portions
of the coefficients in the linear matrix inequalities are accessed.  We
obtain the same result if we define <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> as below.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">16.</span><span class="p">,</span> <span class="mf">7.</span><span class="p">,</span>  <span class="mf">24.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">8.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>
<span class="go">                   7.,  -5.,   1.,  0.,   1.,  -7.,  0.,  0.,  -4.],</span>
<span class="go">                [-14., 2.,   7., -13., -18.,   3.,  0.,  0., -1.,  0.,</span>
<span class="go">                   3.,  13.,  -6.,  0.,  12., -10.,  0.,  0., -28.],</span>
<span class="go">                [  5., 0., -15.,  12.,  -6.,  17.,  0.,  0.,  0., -1.,</span>
<span class="go">                   9.,   6.,  -6.,  0.,  -7.,  -7.,  0.,  0., -11.]])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">,</span>  <span class="mf">12.</span><span class="p">,</span>  <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">14.</span><span class="p">,</span> <span class="o">-</span><span class="mf">13.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>  <span class="mf">0.</span><span class="p">,</span>
<span class="go">                  68., -30., -19.,  0.,  99.,  23.,  0.,  0.,  10.] )</span>
</pre></div>
</div>
</div>
<div class="section" id="quadratic-cone-programs">
<span id="s-coneqp"></span><h2>Quadratic Cone Programs<a class="headerlink" href="#quadratic-cone-programs" title="Permalink to this headline">¶</a></h2>
<dl class="py function">
<dt id="cvxopt.solvers.coneqp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">coneqp</code><span class="sig-paren">(</span><em class="sig-param">P</em>, <em class="sig-param">q</em><span class="optional">[</span>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">dims</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">initvals</em><span class="optional">[</span>, <em class="sig-param">kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.coneqp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a pair of primal and dual quadratic cone programs</p>
<div class="math">
<p><img src="_images/math/6d9473d4787aece2804514f0796e6abeb2ce4dda.png" alt="\begin{array}[t]{ll}
\mbox{minimize}   &amp; (1/2) x^T Px + q^T x \\
\mbox{subject to} &amp; G x + s = h \\
                  &amp; Ax = b \\
                  &amp; s \succeq 0
\end{array}"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/fe748f1ddebc2719b738533481dc2070aa3f8b04.png" alt="\newcommand{\Range}{\mbox{\textrm{range}}}
\begin{array}[t]{ll}
\mbox{maximize}   &amp; -(1/2) (q+G^Tz+A^Ty)^T P^\dagger
                   (q+G^Tz+A^Ty) -h^T z - b^T y \\
\mbox{subject to} &amp; q + G^T z + A^T y \in \Range(P) \\
                  &amp; z \succeq 0.
\end{array}"/></p>
</div><p>The primal variables are <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and the slack variable <img class="math" src="_images/math/106b04b320e75010b1d8029e59244f234f75e6f9.png" alt="s"/>.
The dual variables are <img class="math" src="_images/math/1b5e577d6216dca3af7d87aa122a0b9b360d6cb3.png" alt="y"/> and <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/>.  The inequalities are
interpreted as <img class="math" src="_images/math/4ac9a8351b68de952fda2e33246216aa5edb2818.png" alt="s \in C"/>, <img class="math" src="_images/math/6981ec4aaaf7392f4bf828ef63be506799574e5e.png" alt="z\in C"/>, where <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> is a
cone defined as a Cartesian product of a nonnegative orthant, a number
of second-order cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/03cfea18434ec87caa164206e463d7a230e1cb5c.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
    \cdots \times C_{M+N}"/></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/d767754db8d214ccf0dcaf05b48317d378fbddb5.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
    C_0 &amp; =
        \{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\}, \\
    C_{k+1} &amp; = \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1}
        \; | \; u_0 \geq \|u_1\|_2 \},  \quad k=0,\ldots, M-1, \\
    C_{k+M+1} &amp;= \left\{ \svec(u) \; | \; u \in \symm^{t_k}_+
        \right\}, \quad k=0,\ldots,N-1.
\end{split}"/></p>
</div><p>In this definition, <img class="math" src="_images/math/5866199ac7f27f9fa8f345c8d6bd6f14fc869908.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix
<img class="math" src="_images/math/9b444cf6329a14140aee8ff5a06ff30772cc1c2f.png" alt="u"/> stored as a vector in column major order.  The structure of
<img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/> is specified by <code class="docutils literal notranslate"><span class="pre">dims</span></code>.  This argument is a dictionary with
three fields.</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">dims['l']</span></code>:</dt><dd><p><img class="math" src="_images/math/470aa65888a2971c9346e573f12b37ea406b8ec9.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['q']</span></code>:</dt><dd><p><img class="math" src="_images/math/79b3736681052735beb52087fe8a1b6c188338fb.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</p>
</dd>
<dt><code class="docutils literal notranslate"><span class="pre">dims['s']</span></code>:</dt><dd><p><img class="math" src="_images/math/d706fc3d557d35b283be36ac9e240324b68b34b9.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</p>
</dd>
</dl>
<p>The default value of <code class="docutils literal notranslate"><span class="pre">dims</span></code> is <code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span>
<span class="pre">'s':</span> <span class="pre">[]}</span></code>, i.e., by default the inequality is interpreted as a
componentwise vector inequality.</p>
<p><code class="docutils literal notranslate"><span class="pre">P</span></code> is a square dense or sparse real matrix, representing a positive
semidefinite symmetric matrix in <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code> storage, i.e., only the
lower triangular part of <code class="docutils literal notranslate"><span class="pre">P</span></code> is referenced.  <code class="docutils literal notranslate"><span class="pre">q</span></code> is a real
single-column dense matrix.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are real single-column dense matrices.
<code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">A</span></code> are real dense or sparse matrices.  The number of rows
of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> is equal to</p>
<div class="math">
<p><img src="_images/math/95c7fad2a12f832a0675a00c80c4a8894297d2b8.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2."/></p>
</div><p>The columns of <code class="docutils literal notranslate"><span class="pre">G</span></code> and <code class="docutils literal notranslate"><span class="pre">h</span></code> are vectors in</p>
<div class="math">
<p><img src="_images/math/1e0371cc3025278f588fd7d0ccfcc2510ff2f8cf.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2}  \times \cdots \times
\reals^{t_{N-1}^2},"/></p>
</div><p>where the last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> components represent symmetric matrices stored
in column major order.  The strictly upper triangular entries of these
matrices are not accessed (i.e.,  the symmetric matrices are stored
in the <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code>-type column major order used in the <code class="xref py py-mod docutils literal notranslate"><span class="pre">blas</span></code> and
<code class="xref py py-mod docutils literal notranslate"><span class="pre">lapack</span></code> modules).  The default values for <code class="docutils literal notranslate"><span class="pre">G</span></code>, <code class="docutils literal notranslate"><span class="pre">h</span></code>, <code class="docutils literal notranslate"><span class="pre">A</span></code>,
and <code class="docutils literal notranslate"><span class="pre">b</span></code> are matrices with zero rows, meaning that there are no
inequality or equality constraints.</p>
<p><code class="docutils literal notranslate"><span class="pre">initvals</span></code> is a dictionary with keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> used as an optional starting point.  The
vectors <code class="docutils literal notranslate"><span class="pre">initvals['s']</span></code> and <code class="docutils literal notranslate"><span class="pre">initvals['z']</span></code> must be
strictly positive with respect to the cone <img class="math" src="_images/math/4db5b6e16e06f929ce3f675c5e535d06ffb02ff7.png" alt="C"/>.  If the argument
<code class="docutils literal notranslate"><span class="pre">initvals</span></code> or any the four entries in it are missing, default
starting points are used for the corresponding variables.</p>
<p>The role of the optional argument <code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> is explained in the
section <a class="reference internal" href="#s-conelp-struct"><span class="std std-ref">Exploiting Structure</span></a>.</p>
<p><a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> returns a dictionary that contains the result and
information about the accuracy of the solution.  The most important
fields have keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code>.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> field  is a string
with possible values <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code>.</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code></dt><dd><p>In this case the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries contain primal and dual solutions, which
approximately satisfy</p>
<div class="math">
<p><img src="_images/math/073b4fb9749f6ab5523c701bbe38a97c5fa94288.png" alt="Gx+s = h, \qquad Ax = b, \qquad Px + G^Tz + A^T y + q = 0,

s \succeq 0, \qquad z \succeq 0, \qquad s^T z  = 0."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code></dt><dd><p>This indicates that the algorithm terminated early due to numerical
difficulties or because the maximum number of iterations was
reached.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> entries contain the iterates when the algorithm
terminated.</p>
</dd>
</dl>
<p>The other entries in the output dictionary summarize the accuracy
with which the optimality conditions are satisfied.  The fields
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">objective'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">objective'</span></code>, and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'gap'</span></code> give the primal objective <img class="math" src="_images/math/db7426d70cdd8a4c33c3f1b8f7bdc9ba1b62c43a.png" alt="c^Tx"/>, the dual
objective calculated as</p>
<div class="math">
<p><img src="_images/math/01824df8f8806530b722445b6f9cde3a8e732f07.png" alt="(1/2) x^TPx + q^T x + z^T(Gx-h) + y^T(Ax-b)"/></p>
</div><p>and the gap <img class="math" src="_images/math/bca8217ac2efcad7312d6e496b4e4c82d8d179f6.png" alt="s^Tz"/>.  The field <code class="xref py py-const docutils literal notranslate"><span class="pre">'relative</span> <span class="pre">gap'</span></code> is the
relative gap, defined as</p>
<div class="math">
<p><img src="_images/math/211a6aeaec6adf6a5dd8e0c7de1c4e9f4635ad25.png" alt="\frac{s^Tz}{-\mbox{primal objective}}
\quad \mbox{if\ } \mbox{primal objective} &lt; 0, \qquad
\frac{s^Tz}{\mbox{dual objective}}
\quad \mbox{if\ } \mbox{dual objective} &gt; 0, \qquad"/></p>
</div><p>and <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> otherwise.  The fields
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></code> are
the residuals in the primal and dual equality constraints, defined as</p>
<div class="math">
<p><img src="_images/math/b6c16fed84a824ab88468f81a2b505ac69ad7505.png" alt="\max\{ \frac{\|Gx+s-h\|_2}{\max\{1, \|h\|_2\}},
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \}, \qquad
\frac{\|Px + G^Tz + A^Ty + q\|_2}{\max\{1, \|q\|_2\}},"/></p>
</div><p>respectively.</p>
<p>It is required that the problem is solvable and that</p>
<div class="math">
<p><img src="_images/math/70b640ff0659b7d33287ba001e5b26c6c93a96ba.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank(\left[\begin{array}{c} P \\ G \\ A \end{array}\right]) = n,"/></p>
</div><p>where <img class="math" src="_images/math/141bbefb74014fc5e43499901bf78607ae335583.png" alt="p"/> is the number or rows of <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/> and <img class="math" src="_images/math/5a939c5280da7202ca4531f175a7780ad5e1f80a.png" alt="n"/> is the
number of columns of <img class="math" src="_images/math/89878909dbb648acdc4a44ded1bd982d7bddef5d.png" alt="G"/> and <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/>.</p>
</dd></dl>

<p>As an example, we solve a constrained least-squares problem</p>
<div class="math">
<p><img src="_images/math/a444daac219907b51a5edd730d624c53328d693f.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; \|Ax - b\|_2^2 \\
\mbox{subject to} &amp;  x \succeq 0 \\
                  &amp; \|x\|_2 \leq 1
\end{array}"/></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/68ea4366a8e9dac6f50d5b899ac5c385374d9673.png" alt="A = \left[ \begin{array}{rrr}
    0.3 &amp;  0.6 &amp; -0.3 \\
   -0.4 &amp;  1.2 &amp;  0.0 \\
   -0.2 &amp; -1.7 &amp;  0.6 \\
   -0.4 &amp;  0.3 &amp; -1.2 \\
    1.3 &amp; -0.3 &amp; -2.0
   \end{array} \right], \qquad
b = \left[ \begin{array}{r} 1.5 \\ 0.0 \\ -1.2 \\ -0.7 \\ 0.0
    \end{array} \right]."/></p>
</div><div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">A</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span> <span class="p">[</span> <span class="o">.</span><span class="mi">3</span><span class="p">,</span> <span class="o">-.</span><span class="mi">4</span><span class="p">,</span>  <span class="o">-.</span><span class="mi">2</span><span class="p">,</span>  <span class="o">-.</span><span class="mi">4</span><span class="p">,</span>  <span class="mf">1.3</span> <span class="p">],</span>
<span class="go">                 [ .6, 1.2, -1.7,   .3,  -.3 ],</span>
<span class="go">                 [-.3,  .0,   .6, -1.2, -2.0 ] ])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">b</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span> <span class="mf">1.5</span><span class="p">,</span> <span class="o">.</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.2</span><span class="p">,</span> <span class="o">-.</span><span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">0</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">I</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">I</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mf">1.0</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="n">I</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="p">)),</span> <span class="n">I</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">]</span> <span class="o">+</span> <span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="n">n</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span> <span class="p">[]}</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">x</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">coneqp</span><span class="p">(</span><span class="n">A</span><span class="o">.</span><span class="n">T</span><span class="o">*</span><span class="n">A</span><span class="p">,</span> <span class="o">-</span><span class="n">A</span><span class="o">.</span><span class="n">T</span><span class="o">*</span><span class="n">b</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="go">[ 7.26e-01]</span>
<span class="go">[ 6.18e-01]</span>
<span class="go">[ 3.03e-01]</span>
</pre></div>
</div>
</div>
<div class="section" id="linear-programming">
<span id="s-lpsolver"></span><h2>Linear Programming<a class="headerlink" href="#linear-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a class="reference internal" href="#cvxopt.solvers.lp" title="cvxopt.solvers.lp"><code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span></code></a> is an interface to
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> for linear
programs.  It also provides the option of using the linear programming
solvers from GLPK or MOSEK.</p>
<dl class="py function">
<dt id="cvxopt.solvers.lp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">lp</code><span class="sig-paren">(</span><em class="sig-param">c</em>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">solver</em><span class="optional">[</span>, <em class="sig-param">primalstart</em><span class="optional">[</span>, <em class="sig-param">dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.lp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual linear programs</p>
<div class="math">
<p><img src="_images/math/9f18ba54fa478c728e3a3536166f874c17aa7c04.png" alt="\begin{array}[t]{ll}
\mbox{minimize}   &amp; c^T x \\
\mbox{subject to} &amp; G x + s = h \\
                  &amp; Ax = b \\
                  &amp; s \succeq 0
\end{array}
\qquad\qquad
\begin{array}[t]{ll}
\mbox{maximize}   &amp; -h^T z - b^T y \\
\mbox{subject to} &amp; G^T z + A^T y + c = 0 \\
                  &amp; z \succeq 0.
\end{array}"/></p>
</div><p>The inequalities are componentwise vector inequalities.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">solver</span></code> argument is used to choose among three solvers.  When
it is omitted or <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, the CVXOPT function
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> is
used.  The external solvers GLPK and MOSEK (if installed) can be
selected by setting <code class="docutils literal notranslate"><span class="pre">solver</span></code> to <code class="xref py py-const docutils literal notranslate"><span class="pre">'glpk'</span></code> or <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code>;
see the section <a class="reference internal" href="#s-external"><span class="std std-ref">Optional Solvers</span></a>.  The meaning of the other
arguments and the return value are the same as for
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> called with
<code class="docutils literal notranslate"><span class="pre">dims</span></code> equal to <code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></code>.</p>
<p>The initial values are ignored when <code class="docutils literal notranslate"><span class="pre">solver</span></code> is <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code> or
<code class="xref py py-const docutils literal notranslate"><span class="pre">'glpk'</span></code>.  With the GLPK option, the solver does not return
certificates of primal or dual infeasibility: if the status is
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code> or <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code>, all entries
of the output dictionary are <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>.  If the GLPK or MOSEK
solvers are used, and the code returns with status <code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code>,
all the other fields in the output dictionary are <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>.</p>
</dd></dl>

<p>As a simple example we solve the LP</p>
<div class="math">
<p><img src="_images/math/485e65f87f30e5ab52138c945744fe97e6dd87dc.png" alt="\begin{array}[t]{ll}
\mbox{minimize}   &amp; -4x_1 - 5x_2 \\
\mbox{subject to} &amp;  2x_1 + x_2 \leq 3 \\
                  &amp; x_1 + 2x_2 \leq 3 \\
                  &amp; x_1 \geq 0, \quad x_2 \geq 0.
\end{array}"/></p>
</div><div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">4.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">2.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">],</span> <span class="p">[</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">2.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">]])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">lp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">])</span>
<span class="go">[ 1.00e+00]</span>
<span class="go">[ 1.00e+00]</span>
</pre></div>
</div>
</div>
<div class="section" id="quadratic-programming">
<span id="s-qp"></span><h2>Quadratic Programming<a class="headerlink" href="#quadratic-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a class="reference internal" href="#cvxopt.solvers.qp" title="cvxopt.solvers.qp"><code class="xref py py-func docutils literal notranslate"><span class="pre">qp</span></code></a> is an interface to
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> for quadratic
programs.  It also provides the option of using the quadratic programming
solver from MOSEK.</p>
<dl class="py function">
<dt id="cvxopt.solvers.qp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">qp</code><span class="sig-paren">(</span><em class="sig-param">P</em>, <em class="sig-param">q</em><span class="optional">[</span>, <em class="sig-param">G</em>, <em class="sig-param">h</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">solver</em><span class="optional">[</span>, <em class="sig-param">initvals</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.qp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual convex quadratic programs</p>
<div class="math">
<p><img src="_images/math/ac5ad3214d3caf44e5cc4e9514908ba2a7bb48dc.png" alt="\begin{array}[t]{ll}
\mbox{minimize} &amp; (1/2) x^TPx + q^T x \\
\mbox{subject to} &amp; Gx \preceq h \\ &amp; Ax = b
\end{array}"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/7075b711b50c004803b51912b9dca99d35c65d35.png" alt="\newcommand{\Range}{\mbox{\textrm{range}}}
\begin{array}[t]{ll}
\mbox{maximize}   &amp; -(1/2) (q+G^Tz+A^Ty)^T P^\dagger
                     (q+G^Tz+A^Ty) -h^T z - b^T y \\
\mbox{subject to} &amp; q + G^T z + A^T y \in \Range(P) \\
                  &amp; z \succeq 0.
\end{array}"/></p>
</div><p>The inequalities are componentwise vector inequalities.</p>
<p>The default CVXOPT solver is used when the <code class="docutils literal notranslate"><span class="pre">solver</span></code> argument is
absent or <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>.  The MOSEK solver (if installed) can be
selected by setting <code class="docutils literal notranslate"><span class="pre">solver</span></code> to <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code>; see the
section <a class="reference internal" href="#s-external"><span class="std std-ref">Optional Solvers</span></a>.  The meaning of the other arguments and the
return value is the same as for
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> called with <cite>dims</cite>
equal to <code class="docutils literal notranslate"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></code>.</p>
<p>When <code class="docutils literal notranslate"><span class="pre">solver</span></code> is <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code>, the initial values are ignored,
and the <code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code> string in the solution dictionary can take
four possible values: <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'unknown'</span></code>.
<code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code>.</p>
<dl>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code></dt><dd><p>This means that a certificate of primal infeasibility has been
found.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code> entries are
<code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, and the <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> entries are
vectors that approximately satisfy</p>
<div class="math">
<p><img src="_images/math/82a55744f92063b61aaffddd2380a5cbf8a2b1c6.png" alt="G^Tz + A^T y = 0, \qquad h^Tz + b^Ty = -1, \qquad z \succeq 0."/></p>
</div></dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code></dt><dd><p>This means that a certificate of dual infeasibility has been found.
The <code class="xref py py-const docutils literal notranslate"><span class="pre">'z'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code> entries are <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>, and
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'s'</span></code> entries are vectors that
approximately satisfy</p>
<div class="math">
<p><img src="_images/math/e50141a6a4a3490d1acc94e54f7de36ac5f7e8eb.png" alt="Px = 0, \qquad q^Tx = -1, \qquad Gx + s = 0, \qquad Ax=0,
\qquad s \succeq  0."/></p>
</div></dd>
</dl>
</dd></dl>

<p>As an example we compute the trade-off curve on page 187 of the book
<a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex Optimization</a>,
by solving the quadratic program</p>
<div class="math">
<p><img src="_images/math/cd4c2f3674b5e0def3984a035f720209c8391074.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize}   &amp; -\bar p^T x + \mu x^T S x \\
\mbox{subject to} &amp; \ones^T x = 1, \quad x \succeq 0
\end{array}"/></p>
</div><p>for a sequence of positive values of <img class="math" src="_images/math/4a3598141469c2555591e66606a1b86d4ec6dca9.png" alt="\mu"/>.  The code below computes
the trade-off curve and produces two figures using the
<a class="reference external" href="http://matplotlib.sourceforge.net">Matplotlib</a> package.</p>
<a class="reference internal image-reference" href="_images/portfolio2.png"><img alt="_images/portfolio2.png" src="_images/portfolio2.png" style="width: 400px;" /></a>
<a class="reference internal image-reference" href="_images/portfolio1.png"><img alt="_images/portfolio1.png" src="_images/portfolio1.png" style="width: 400px;" /></a>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">math</span> <span class="kn">import</span> <span class="n">sqrt</span>
<span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span>
<span class="kn">from</span> <span class="nn">cvxopt.blas</span> <span class="kn">import</span> <span class="n">dot</span>
<span class="kn">from</span> <span class="nn">cvxopt.solvers</span> <span class="kn">import</span> <span class="n">qp</span>
<span class="kn">import</span> <span class="nn">pylab</span>

<span class="c1"># Problem data.</span>
<span class="n">n</span> <span class="o">=</span> <span class="mi">4</span>
<span class="n">S</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">4e-2</span><span class="p">,</span>  <span class="mf">6e-3</span><span class="p">,</span> <span class="o">-</span><span class="mf">4e-3</span><span class="p">,</span>    <span class="mf">0.0</span> <span class="p">],</span>
            <span class="p">[</span> <span class="mf">6e-3</span><span class="p">,</span>  <span class="mf">1e-2</span><span class="p">,</span>  <span class="mf">0.0</span><span class="p">,</span>     <span class="mf">0.0</span> <span class="p">],</span>
            <span class="p">[</span><span class="o">-</span><span class="mf">4e-3</span><span class="p">,</span>  <span class="mf">0.0</span><span class="p">,</span>   <span class="mf">2.5e-3</span><span class="p">,</span>  <span class="mf">0.0</span> <span class="p">],</span>
            <span class="p">[</span> <span class="mf">0.0</span><span class="p">,</span>   <span class="mf">0.0</span><span class="p">,</span>   <span class="mf">0.0</span><span class="p">,</span>     <span class="mf">0.0</span> <span class="p">]])</span>
<span class="n">pbar</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">.</span><span class="mi">12</span><span class="p">,</span> <span class="o">.</span><span class="mi">10</span><span class="p">,</span> <span class="o">.</span><span class="mi">07</span><span class="p">,</span> <span class="o">.</span><span class="mi">03</span><span class="p">])</span>
<span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">G</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="n">A</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">b</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">)</span>

<span class="c1"># Compute trade-off.</span>
<span class="n">N</span> <span class="o">=</span> <span class="mi">100</span>
<span class="n">mus</span> <span class="o">=</span> <span class="p">[</span> <span class="mi">10</span><span class="o">**</span><span class="p">(</span><span class="mf">5.0</span><span class="o">*</span><span class="n">t</span><span class="o">/</span><span class="n">N</span><span class="o">-</span><span class="mf">1.0</span><span class="p">)</span> <span class="k">for</span> <span class="n">t</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">]</span>
<span class="n">portfolios</span> <span class="o">=</span> <span class="p">[</span> <span class="n">qp</span><span class="p">(</span><span class="n">mu</span><span class="o">*</span><span class="n">S</span><span class="p">,</span> <span class="o">-</span><span class="n">pbar</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">]</span> <span class="k">for</span> <span class="n">mu</span> <span class="ow">in</span> <span class="n">mus</span> <span class="p">]</span>
<span class="n">returns</span> <span class="o">=</span> <span class="p">[</span> <span class="n">dot</span><span class="p">(</span><span class="n">pbar</span><span class="p">,</span><span class="n">x</span><span class="p">)</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">risks</span> <span class="o">=</span> <span class="p">[</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dot</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">S</span><span class="o">*</span><span class="n">x</span><span class="p">))</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>

<span class="c1"># Plot trade-off curve and optimal allocations.</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">figure</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">facecolor</span><span class="o">=</span><span class="s1">&#39;w&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">plot</span><span class="p">(</span><span class="n">risks</span><span class="p">,</span> <span class="n">returns</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xlabel</span><span class="p">(</span><span class="s1">&#39;standard deviation&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">ylabel</span><span class="p">(</span><span class="s1">&#39;expected return&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="mi">0</span><span class="p">,</span> <span class="mf">0.2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mf">0.15</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">title</span><span class="p">(</span><span class="s1">&#39;Risk-return trade-off curve (fig 4.12)&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([</span><span class="mf">0.00</span><span class="p">,</span> <span class="mf">0.05</span><span class="p">,</span> <span class="mf">0.10</span><span class="p">,</span> <span class="mf">0.15</span><span class="p">])</span>

<span class="n">pylab</span><span class="o">.</span><span class="n">figure</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">facecolor</span><span class="o">=</span><span class="s1">&#39;w&#39;</span><span class="p">)</span>
<span class="n">c1</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c2</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c3</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c4</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span> <span class="o">+</span> <span class="p">[</span><span class="o">.</span><span class="mi">20</span><span class="p">],</span> <span class="n">c1</span> <span class="o">+</span> <span class="p">[</span><span class="mf">0.0</span><span class="p">],</span> <span class="s1">&#39;#F0F0F0&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c2</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c1</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s1">&#39;#D0D0D0&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c3</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c2</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s1">&#39;#F0F0F0&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c4</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c3</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s1">&#39;#D0D0D0&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.2</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xlabel</span><span class="p">(</span><span class="s1">&#39;standard deviation&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">ylabel</span><span class="p">(</span><span class="s1">&#39;allocation&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">15</span><span class="p">,</span><span class="o">.</span><span class="mi">5</span><span class="p">,</span><span class="s1">&#39;x1&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">10</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s1">&#39;x2&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">05</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s1">&#39;x3&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">01</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s1">&#39;x4&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">title</span><span class="p">(</span><span class="s1">&#39;Optimal allocations (fig 4.12)&#39;</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">show</span><span class="p">()</span>
</pre></div>
</div>
</div>
<div class="section" id="second-order-cone-programming">
<span id="s-socpsolver"></span><h2>Second-Order Cone Programming<a class="headerlink" href="#second-order-cone-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a class="reference internal" href="#cvxopt.solvers.socp" title="cvxopt.solvers.socp"><code class="xref py py-func docutils literal notranslate"><span class="pre">socp</span></code></a> is a simpler interface to
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> for
cone programs with no linear matrix inequality constraints.</p>
<dl class="py function">
<dt id="cvxopt.solvers.socp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">socp</code><span class="sig-paren">(</span><em class="sig-param">c</em><span class="optional">[</span>, <em class="sig-param">Gl</em>, <em class="sig-param">hl</em><span class="optional">[</span>, <em class="sig-param">Gq</em>, <em class="sig-param">hq</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">solver</em><span class="optional">[</span>, <em class="sig-param">primalstart</em><span class="optional">[</span>, <em class="sig-param">dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.socp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual second-order cone programs</p>
<div class="math">
<p><img src="_images/math/32cab048b453581f0ca59dc31e33e56b7c8b3a0e.png" alt="\begin{array}[t]{ll}
\mbox{minimize}   &amp; c^T x \\
\mbox{subject to} &amp; G_k x + s_k = h_k, \quad k = 0, \ldots, M  \\
                  &amp; Ax = b \\
                  &amp; s_0 \succeq 0 \\
                  &amp; s_{k0} \geq \|s_{k1}\|_2, \quad k = 1,\ldots,M
\end{array}"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/56ebcc22b7fc4da65f58f0819b21a4c7da613bd4.png" alt="\begin{array}[t]{ll}
\mbox{maximize}   &amp; - \sum_{k=0}^M h_k^Tz_k - b^T y \\
\mbox{subject to} &amp; \sum_{k=0}^M G_k^T z_k + A^T y + c = 0 \\
                  &amp; z_0 \succeq 0 \\
                  &amp; z_{k0} \geq \|z_{k1}\|_2, \quad k=1,\ldots,M.
\end{array}"/></p>
</div><p>The inequalities</p>
<div class="math">
<p><img src="_images/math/d56da07a3d18c9fc980ecc0a9696603bd8d8dcd2.png" alt="s_0 \succeq 0, \qquad z_0 \succeq 0"/></p>
</div><p>are componentwise vector inequalities.  In the other inequalities, it
is assumed that the variables are partitioned as</p>
<div class="math">
<p><img src="_images/math/1337abb9748b0985f66823f48527ff07692b910a.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
s_k = (s_{k0}, s_{k1}) \in\reals\times\reals^{r_{k}-1}, \qquad
z_k = (z_{k0}, z_{k1}) \in\reals\times\reals^{r_{k}-1}, \qquad
k=1,\ldots,M."/></p>
</div><p>The input argument <code class="docutils literal notranslate"><span class="pre">c</span></code> is a real single-column dense matrix.  The
arguments <code class="docutils literal notranslate"><span class="pre">Gl</span></code> and <code class="docutils literal notranslate"><span class="pre">hl</span></code> are the coefficient matrix <img class="math" src="_images/math/c8ed607e197ca518179a4030e6aed34c1d339e7e.png" alt="G_0"/> and
the right-hand side <img class="math" src="_images/math/6c74a61cdf90a8a3b50f62a58910b84d0fe23678.png" alt="h_0"/> of the componentwise inequalities.
<code class="docutils literal notranslate"><span class="pre">Gl</span></code> is a real dense or sparse matrix; <code class="docutils literal notranslate"><span class="pre">hl</span></code> is a real single-column
dense matrix.  The default values for <code class="docutils literal notranslate"><span class="pre">Gl</span></code> and <code class="docutils literal notranslate"><span class="pre">hl</span></code> are matrices
with zero rows.</p>
<p>The argument <code class="docutils literal notranslate"><span class="pre">Gq</span></code> is a list of <img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/> dense or sparse matrices
<img class="math" src="_images/math/cbb49321318d94ba656d1ce115187d55c90322b4.png" alt="G_1"/>, …, <img class="math" src="_images/math/1e45a7a687f92b2a29b62ce1dddb23a8eefeedca.png" alt="G_M"/>.  The argument <code class="docutils literal notranslate"><span class="pre">hq</span></code> is a list of
<img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/> dense single-column matrices <img class="math" src="_images/math/1e3c4fd71e54eca8ee4a7928ebfd8e6c0bc70d31.png" alt="h_1"/>, ldots,
<img class="math" src="_images/math/b9114cc1138ec152eae394b47fa104b1ee1ee4b9.png" alt="h_M"/>.  The elements of <code class="docutils literal notranslate"><span class="pre">Gq</span></code> and <code class="docutils literal notranslate"><span class="pre">hq</span></code> must have at least one
row.  The default values of <code class="docutils literal notranslate"><span class="pre">Gq</span></code> and <code class="docutils literal notranslate"><span class="pre">hq</span></code> are empty lists.</p>
<p><code class="docutils literal notranslate"><span class="pre">A</span></code> is dense or sparse matrix and <code class="docutils literal notranslate"><span class="pre">b</span></code> is a single-column dense
matrix.  The default values for <code class="docutils literal notranslate"><span class="pre">A</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are matrices with
zero rows.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">solver</span></code> argument is used to choose between two solvers: the
CVXOPT <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> solver (used when
<code class="docutils literal notranslate"><span class="pre">solver</span></code> is absent or equal
to <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code> and the external solver MOSEK (<code class="docutils literal notranslate"><span class="pre">solver</span></code> is
<code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code>); see the section <a class="reference internal" href="#s-external"><span class="std std-ref">Optional Solvers</span></a>.  With the
<code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code> option the code does not accept problems with equality
constraints.</p>
<p><code class="docutils literal notranslate"><span class="pre">primalstart</span></code> and <code class="docutils literal notranslate"><span class="pre">dualstart</span></code> are dictionaries with optional
primal, respectively, dual starting points.  <code class="docutils literal notranslate"><span class="pre">primalstart</span></code> has
elements <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sq'</span></code>.
<code class="docutils literal notranslate"><span class="pre">primalstart['x']</span></code> and <code class="docutils literal notranslate"><span class="pre">primalstart['sl']</span></code> are
single-column dense matrices with the initial values of <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and
<img class="math" src="_images/math/8fb1fc12384d9c1b73b81b87315f7654511a2c0e.png" alt="s_0"/>;  <code class="docutils literal notranslate"><span class="pre">primalstart['sq']</span></code> is a list of single-column
matrices with the initial values of <img class="math" src="_images/math/41088e732877c4491fed8b82e3b2b39c8638ee16.png" alt="s_1"/>, ldots, <img class="math" src="_images/math/ddefb5b246529cd9459225d23c9a2444a37f26fa.png" alt="s_M"/>.
The initial values must satisfy the inequalities in the primal problem
strictly, but not necessarily the equality constraints.</p>
<p><code class="docutils literal notranslate"><span class="pre">dualstart</span></code> has elements <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zq'</span></code>.
<code class="docutils literal notranslate"><span class="pre">dualstart['y']</span></code> and <code class="docutils literal notranslate"><span class="pre">dualstart['zl']</span></code> are single-column
dense matrices with the initial values of <img class="math" src="_images/math/1b5e577d6216dca3af7d87aa122a0b9b360d6cb3.png" alt="y"/> and <img class="math" src="_images/math/b7dd8acc0d0af36b58c42bc14eeeca05c6286fba.png" alt="z_0"/>.
<code class="docutils literal notranslate"><span class="pre">dualstart['zq']</span></code> is a list of single-column matrices with the
initial values of <img class="math" src="_images/math/25e1d0f27471fc48a5066ec25b700df2e725728e.png" alt="z_1"/>, ldots, <img class="math" src="_images/math/264ee9c3c31874f04bd683e78a3a7777f20cb88b.png" alt="z_M"/>.  These values must
satisfy the dual inequalities strictly, but not necessarily the
equality constraint.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">primalstart</span></code> and <code class="docutils literal notranslate"><span class="pre">dualstart</span></code> are ignored when the
MOSEK solver is used.</p>
<p><a class="reference internal" href="#cvxopt.solvers.socp" title="cvxopt.solvers.socp"><code class="xref py py-func docutils literal notranslate"><span class="pre">socp</span></code></a> returns a dictionary that include entries with keys
<code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sq'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zq'</span></code>.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code> and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code> fields are matrices with the primal slacks and dual
variables associated with the componentwise linear inequalities.
The <code class="xref py py-const docutils literal notranslate"><span class="pre">'sq'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zq'</span></code> fields are lists with the primal
slacks and dual variables associated with the second-order cone
inequalities.  The other entries in the output dictionary have the
same meaning as in the output of
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a>.</p>
</dd></dl>

<p>As an example, we solve  the second-order cone program</p>
<div class="math">
<p><img src="_images/math/13abf6ff1ab819235d06737ba4cc4b56c12cf29f.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; -2x_1 + x_2 + 5x_3 \\*[2ex]
\mbox{subject to} &amp; \left\| \left[\begin{array}{c}
    -13 x_1 +  3 x_2 + 5 x_3 - 3 \\
    -12 x_1 + 12 x_2 - 6 x_3 - 2 \end{array}\right] \right\|_2
     \leq -12 x_1 - 6 x_2 + 5x_3 - 12  \\*[2ex]
                   &amp; \left\| \left[\begin{array}{c}
     -3 x_1 +  6 x_2 + 2 x_3    \\
        x_1 +  9 x_2 + 2 x_3 + 3 \\
       -x_1 - 19 x_2 + 3 x_3 - 42 \end{array}\right] \right\|_2
     \leq -3x_1 + 6x_2 - 10x_3 + 27.
\end{array}"/></p>
</div><div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[[</span><span class="mf">12.</span><span class="p">,</span> <span class="mf">13.</span><span class="p">,</span> <span class="mf">12.</span><span class="p">],</span> <span class="p">[</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">12.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">5.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">,</span> <span class="mf">6.</span><span class="p">]]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[[</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">19.</span><span class="p">],</span> <span class="p">[</span><span class="mf">10.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">]]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span><span class="o">-</span><span class="mf">12.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">]</span> <span class="p">),</span>  <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span><span class="mf">27.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">42.</span><span class="p">]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">socp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">Gq</span> <span class="o">=</span> <span class="n">G</span><span class="p">,</span> <span class="n">hq</span> <span class="o">=</span> <span class="n">h</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;status&#39;</span><span class="p">]</span>
<span class="go">optimal</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">])</span>
<span class="go">[-5.02e+00]</span>
<span class="go">[-5.77e+00]</span>
<span class="go">[-8.52e+00]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;zq&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span>
<span class="go">[ 1.34e+00]</span>
<span class="go">[-7.63e-02]</span>
<span class="go">[-1.34e+00]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;zq&#39;</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span>
<span class="go">[ 1.02e+00]</span>
<span class="go">[ 4.02e-01]</span>
<span class="go">[ 7.80e-01]</span>
<span class="go">[-5.17e-01]</span>
</pre></div>
</div>
</div>
<div class="section" id="semidefinite-programming">
<span id="s-sdpsolver"></span><h2>Semidefinite Programming<a class="headerlink" href="#semidefinite-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a class="reference internal" href="#cvxopt.solvers.sdp" title="cvxopt.solvers.sdp"><code class="xref py py-func docutils literal notranslate"><span class="pre">sdp</span></code></a> is a simple interface to
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> for cone
programs with no second-order cone constraints.  It also provides the
option of using the DSDP semidefinite programming solver.</p>
<dl class="py function">
<dt id="cvxopt.solvers.sdp">
<code class="sig-prename descclassname">cvxopt.solvers.</code><code class="sig-name descname">sdp</code><span class="sig-paren">(</span><em class="sig-param">c</em><span class="optional">[</span>, <em class="sig-param">Gl</em>, <em class="sig-param">hl</em><span class="optional">[</span>, <em class="sig-param">Gs</em>, <em class="sig-param">hs</em><span class="optional">[</span>, <em class="sig-param">A</em>, <em class="sig-param">b</em><span class="optional">[</span>, <em class="sig-param">solver</em><span class="optional">[</span>, <em class="sig-param">primalstart</em><span class="optional">[</span>, <em class="sig-param">dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#cvxopt.solvers.sdp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual semidefinite programs</p>
<div class="math">
<p><img src="_images/math/191bc203fa207a53847c892bc9bc56a69a1c60c1.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
\begin{array}[t]{ll}
\mbox{minimize}   &amp; c^T x \\
\mbox{subject to} &amp; G_0 x + s_0 = h_0 \\
                  &amp; G_k x + \svec{(s_k)} = \svec{(h_k)},
                    \quad k = 1, \ldots, N  \\
                  &amp; Ax = b \\
                  &amp; s_0 \succeq 0 \\
                  &amp; s_k \succeq 0, \quad k=1,\ldots,N
\end{array}"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/2c0f91e60d2f13fdeba173121a264d745555e902.png" alt="\newcommand{\Tr}{\mathop{\mathbf{tr}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\begin{array}[t]{ll}
\mbox{maximize}   &amp; -h_0^Tz_0 - \sum_{k=1}^N \Tr(h_kz_k) - b^Ty \\
\mbox{subject to} &amp; G_0^Tz_0 + \sum_{k=1}^N G_k^T \svec(z_k) +
                     A^T y + c = 0 \\
                  &amp; z_0 \succeq 0 \\
                  &amp; z_k \succeq 0, \quad k=1,\ldots,N.
\end{array}"/></p>
</div><p>The inequalities</p>
<div class="math">
<p><img src="_images/math/d56da07a3d18c9fc980ecc0a9696603bd8d8dcd2.png" alt="s_0 \succeq 0, \qquad z_0 \succeq 0"/></p>
</div><p>are componentwise vector inequalities.  The other inequalities are
matrix inequalities (ie, the require the left-hand sides to be
positive semidefinite).  We use the notation <img class="math" src="_images/math/60d0a6fc7c07bee2dc81830096d4d310add8f5eb.png" alt="\mathbf{vec}(z)"/>
to denote a symmetric matrix <img class="math" src="_images/math/8d051150f8669295ecdbe92367941012175a824d.png" alt="z"/> stored in column major order
as a column vector.</p>
<p>The input argument <code class="docutils literal notranslate"><span class="pre">c</span></code> is a real single-column dense matrix.  The
arguments <code class="docutils literal notranslate"><span class="pre">Gl</span></code> and <code class="docutils literal notranslate"><span class="pre">hl</span></code> are the coefficient matrix <img class="math" src="_images/math/c8ed607e197ca518179a4030e6aed34c1d339e7e.png" alt="G_0"/> and
the right-hand side <img class="math" src="_images/math/6c74a61cdf90a8a3b50f62a58910b84d0fe23678.png" alt="h_0"/> of the componentwise inequalities.
<code class="docutils literal notranslate"><span class="pre">Gl</span></code> is a real dense or sparse matrix;  <code class="docutils literal notranslate"><span class="pre">hl</span></code> is a real
single-column dense matrix.   The default values for <code class="docutils literal notranslate"><span class="pre">Gl</span></code> and <code class="docutils literal notranslate"><span class="pre">hl</span></code>
are matrices with zero rows.</p>
<p><code class="docutils literal notranslate"><span class="pre">Gs</span></code> and <code class="docutils literal notranslate"><span class="pre">hs</span></code> are lists of length <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> that specify the
linear matrix inequality constraints.  <code class="docutils literal notranslate"><span class="pre">Gs</span></code> is a list of <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/>
dense or sparse real matrices <img class="math" src="_images/math/cbb49321318d94ba656d1ce115187d55c90322b4.png" alt="G_1"/>, ldots, <img class="math" src="_images/math/1e45a7a687f92b2a29b62ce1dddb23a8eefeedca.png" alt="G_M"/>.  The
columns of these matrices can be interpreted as symmetric matrices
stored in column major order, using the BLAS <code class="xref py py-const docutils literal notranslate"><span class="pre">'L'</span></code>-type storage
(i.e., only the entries corresponding to lower triangular positions
are accessed).  <code class="docutils literal notranslate"><span class="pre">hs</span></code> is a list of <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> dense symmetric matrices
<img class="math" src="_images/math/1e3c4fd71e54eca8ee4a7928ebfd8e6c0bc70d31.png" alt="h_1"/>, ldots, <img class="math" src="_images/math/1cdcc96e18c62f3865d8d43ada0619823c8bcb33.png" alt="h_N"/>.  Only the lower triangular elements
of these matrices are accessed.  The default values for <code class="docutils literal notranslate"><span class="pre">Gs</span></code> and
<code class="docutils literal notranslate"><span class="pre">hs</span></code> are empty lists.</p>
<p><code class="docutils literal notranslate"><span class="pre">A</span></code> is a dense or sparse matrix and <code class="docutils literal notranslate"><span class="pre">b</span></code> is a single-column dense
matrix.  The default values for <code class="docutils literal notranslate"><span class="pre">A</span></code> and <code class="docutils literal notranslate"><span class="pre">b</span></code> are matrices with zero
rows.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">solver</span></code> argument is used to choose between two solvers: the
CVXOPT <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> solver
(used when <code class="docutils literal notranslate"><span class="pre">solver</span></code> is absent or equal
to <code class="xref py py-const docutils literal notranslate"><span class="pre">None</span></code>) and the external solver DSDP5 (<code class="docutils literal notranslate"><span class="pre">solver</span></code> is
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dsdp'</span></code>); see the section <a class="reference internal" href="#s-external"><span class="std std-ref">Optional Solvers</span></a>.  With the
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dsdp'</span></code> option the code does not accept problems with equality
constraints.</p>
<p>The optional argument <code class="docutils literal notranslate"><span class="pre">primalstart</span></code> is a dictionary with keys
<code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, and <code class="xref py py-const docutils literal notranslate"><span class="pre">'ss'</span></code>, used as an optional
primal starting point.  <code class="docutils literal notranslate"><span class="pre">primalstart['x']</span></code> and
<code class="docutils literal notranslate"><span class="pre">primalstart['sl']</span></code> are single-column dense matrices with the
initial values of <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and <img class="math" src="_images/math/8fb1fc12384d9c1b73b81b87315f7654511a2c0e.png" alt="s_0"/>;
<code class="docutils literal notranslate"><span class="pre">primalstart['ss']</span></code> is a list of square matrices with the initial
values of <img class="math" src="_images/math/41088e732877c4491fed8b82e3b2b39c8638ee16.png" alt="s_1"/>, ldots, <img class="math" src="_images/math/581060bbfd7546835e4dd199b1cfe83a2401e636.png" alt="s_N"/>.  The initial values must
satisfy the inequalities in the primal problem strictly, but not
necessarily the equality constraints.</p>
<p><code class="docutils literal notranslate"><span class="pre">dualstart</span></code> is a dictionary with keys <code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'zs'</span></code>, used as an optional dual starting point.
<code class="docutils literal notranslate"><span class="pre">dualstart['y']</span></code> and <code class="docutils literal notranslate"><span class="pre">dualstart['zl']</span></code> are single-column
dense matrices with the initial values of <img class="math" src="_images/math/1b5e577d6216dca3af7d87aa122a0b9b360d6cb3.png" alt="y"/> and <img class="math" src="_images/math/b7dd8acc0d0af36b58c42bc14eeeca05c6286fba.png" alt="z_0"/>.
<code class="docutils literal notranslate"><span class="pre">dualstart['zs']</span></code> is a list of square matrices with the initial
values of <img class="math" src="_images/math/25e1d0f27471fc48a5066ec25b700df2e725728e.png" alt="z_1"/>, ldots, <img class="math" src="_images/math/ecd00043b2c4fdc2473d664cbbe67fee8dd18c80.png" alt="z_N"/>.  These values must satisfy
the dual inequalities strictly, but not necessarily the equality
constraint.</p>
<p>The arguments <code class="docutils literal notranslate"><span class="pre">primalstart</span></code> and <code class="docutils literal notranslate"><span class="pre">dualstart</span></code> are ignored when the
DSDP solver is used.</p>
<p><a class="reference internal" href="#cvxopt.solvers.sdp" title="cvxopt.solvers.sdp"><code class="xref py py-func docutils literal notranslate"><span class="pre">sdp</span></code></a> returns a dictionary that includes entries with keys
<code class="xref py py-const docutils literal notranslate"><span class="pre">'status'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'x'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'ss'</span></code>,
<code class="xref py py-const docutils literal notranslate"><span class="pre">'y'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'ss'</span></code>.  The <code class="xref py py-const docutils literal notranslate"><span class="pre">'sl'</span></code> and
<code class="xref py py-const docutils literal notranslate"><span class="pre">'zl'</span></code> fields are matrices with the primal slacks and dual
variables associated with the componentwise linear inequalities.
The <code class="xref py py-const docutils literal notranslate"><span class="pre">'ss'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'zs'</span></code> fields are lists with the primal
slacks and dual variables associated with the second-order cone
inequalities.  The other entries in the output dictionary have the
same meaning as in the output of
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a>.</p>
</dd></dl>

<p>We illustrate the calling sequence with a small example.</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/84e264805077d2cf923fe75d31e2ed50021618da.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; x_1 - x_2 + x_3 \\
\mbox{subject to}
    &amp; x_1 \left[ \begin{array}{cc}
              -7 &amp;  -11 \\ -11 &amp;  3
          \end{array}\right] +
      x_2 \left[ \begin{array}{cc}
              7 &amp; -18 \\ -18 &amp; 8
          \end{array}\right] +
      x_3 \left[ \begin{array}{cc}
              -2 &amp; -8 \\ -8 &amp; 1
          \end{array}\right] \preceq
      \left[ \begin{array}{cc}
              33 &amp; -9 \\ -9 &amp; 26
          \end{array}\right] \\*[1ex]
      &amp; x_1 \left[ \begin{array}{ccc}
              -21 &amp; -11 &amp; 0 \\
              -11 &amp;  10 &amp; 8 \\
                0 &amp;   8 &amp; 5
          \end{array}\right] +
      x_2 \left[ \begin{array}{ccc}
                0 &amp;  10 &amp;  16 \\
               10 &amp; -10 &amp; -10 \\
               16 &amp; -10 &amp; 3
          \end{array}\right] +
      x_3 \left[ \begin{array}{ccc}
               -5  &amp; 2 &amp; -17 \\
                2  &amp; -6 &amp; 8 \\
               -17 &amp; 8 &amp; 6
           \end{array}\right]  \preceq
      \left[ \begin{array}{ccc}
               14 &amp;  9 &amp; 40 \\
                9  &amp; 91 &amp; 10 \\
               40 &amp; 10 &amp; 15
          \end{array} \right]
\end{array}"/></p>
</div></div></blockquote>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">1.</span><span class="p">,</span><span class="o">-</span><span class="mf">1.</span><span class="p">,</span><span class="mf">1.</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">7.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">],</span>
<span class="go">                  [ 7., -18., -18., 8.],</span>
<span class="go">                  [-2.,  -8.,  -8., 1.]]) ]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">21.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span>  <span class="mf">10.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">],</span>
<span class="go">                   [  0.,  10.,  16.,  10., -10., -10.,  16., -10., 3.],</span>
<span class="go">                   [ -5.,   2., -17.,   2.,  -6.,   8., -17.,  8., 6.]]) ]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">33.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">26.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">14.</span><span class="p">,</span> <span class="mf">9.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">],</span> <span class="p">[</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">91.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">],</span> <span class="p">[</span><span class="mf">40.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">15.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">sdp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">Gs</span><span class="o">=</span><span class="n">G</span><span class="p">,</span> <span class="n">hs</span><span class="o">=</span><span class="n">h</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">])</span>
<span class="go">[-3.68e-01]</span>
<span class="go">[ 1.90e+00]</span>
<span class="go">[-8.88e-01]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;zs&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span>
<span class="go">[ 3.96e-03 -4.34e-03]</span>
<span class="go">[-4.34e-03  4.75e-03]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">sol</span><span class="p">[</span><span class="s1">&#39;zs&#39;</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span>
<span class="go">[ 5.58e-02 -2.41e-03  2.42e-02]</span>
<span class="go">[-2.41e-03  1.04e-04 -1.05e-03]</span>
<span class="go">[ 2.42e-02 -1.05e-03  1.05e-02]</span>
</pre></div>
</div>
<p>Only the entries in <code class="docutils literal notranslate"><span class="pre">Gs</span></code> and <code class="docutils literal notranslate"><span class="pre">hs</span></code> that correspond to lower triangular
entries need to be provided, so in the example <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">G</span></code> may also be
defined as follows.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">7.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">],</span>
<span class="go">                  [ 7., -18., 0., 8.],</span>
<span class="go">                  [-2.,  -8., 0., 1.]]) ]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">21.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span>   <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span>  <span class="mf">10.</span><span class="p">,</span>   <span class="mf">8.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">],</span>
<span class="go">                   [  0.,  10.,  16., 0., -10., -10., 0., 0., 3.],</span>
<span class="go">                   [ -5.,   2., -17., 0.,  -6.,   8., 0., 0., 6.]]) ]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">33.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">26.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">h</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">14.</span><span class="p">,</span> <span class="mf">9.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">91.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">15.</span><span class="p">]])</span> <span class="p">]</span>
</pre></div>
</div>
</div>
<div class="section" id="exploiting-structure">
<span id="s-conelp-struct"></span><h2>Exploiting Structure<a class="headerlink" href="#exploiting-structure" title="Permalink to this headline">¶</a></h2>
<p>By default, the functions
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> exploit no
problem structure except (to some limited extent) sparsity.  Two mechanisms
are provided for implementing customized solvers that take advantage of
problem structure.</p>
<dl>
<dt><strong>Providing a function for solving KKT equations</strong></dt><dd><p>The most expensive step of each iteration of
<a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> or
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> is the solution of a set of
linear equations (<em>KKT equations</em>) of the form</p>
<div class="math" id="equation-e-conelp-kkt">
<p><span class="eqno">(1)<a class="headerlink" href="#equation-e-conelp-kkt" title="Permalink to this equation">¶</a></span><img src="_images/math/3157de5f84013f57240cf058275c3ae9deb3287a.png" alt="\left[\begin{array}{ccc}
    P &amp; A^T &amp; G^T \\
    A &amp; 0   &amp; 0  \\
    G &amp; 0   &amp; -W^T W
\end{array}\right]
\left[\begin{array}{c} u_x \\ u_y \\ u_z \end{array}\right]
=
\left[\begin{array}{c} b_x \\ b_y \\ b_z \end{array}\right]"/></p>
</div><p>(with <img class="math" src="_images/math/036001c78514c5de2ab5c899cb2b005a905ba3a5.png" alt="P = 0"/> in <code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code>).  The matrix <img class="math" src="_images/math/1fbee781f84569077719a167b64e12064360fac1.png" alt="W"/> depends
on the current iterates and is defined as follows.  We use the notation
of the sections <a class="reference internal" href="#s-conelp"><span class="std std-ref">Linear Cone Programs</span></a> and <a class="reference internal" href="#s-coneqp"><span class="std std-ref">Quadratic Cone Programs</span></a>.  Let</p>
<div class="math">
<p><img src="_images/math/6565000626ccf19f09a9258e78e141cb5ce46180.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
u = \left(u_\mathrm{l}, \; u_{\mathrm{q},0}, \; \ldots, \;
    u_{\mathrm{q},M-1}, \; \svec{(u_{\mathrm{s},0})}, \;
    \ldots, \; \svec{(u_{\mathrm{s},N-1})}\right), \qquad

\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\symm}{{\mbox{\bf S}}}
u_\mathrm{l} \in\reals^l, \qquad
u_{\mathrm{q},k} \in\reals^{r_k}, \quad k = 0,\ldots,M-1, \qquad
u_{\mathrm{s},k} \in\symm^{t_k},  \quad k = 0,\ldots,N-1."/></p>
</div><p>Then <img class="math" src="_images/math/1fbee781f84569077719a167b64e12064360fac1.png" alt="W"/> is a block-diagonal matrix,</p>
<div class="math">
<p><img src="_images/math/ed29c4b1667b0282bad6523664351811e0f23dab.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
Wu = \left( W_\mathrm{l} u_\mathrm{l}, \;
    W_{\mathrm{q},0} u_{\mathrm{q},0}, \; \ldots, \;
    W_{\mathrm{q},M-1} u_{\mathrm{q},M-1},\;
    W_{\mathrm{s},0} \svec{(u_{\mathrm{s},0})}, \; \ldots, \;
    W_{\mathrm{s},N-1} \svec{(u_{\mathrm{s},N-1})} \right)"/></p>
</div><p>with the following diagonal blocks.</p>
<ul>
<li><p>The first block is a <em>positive diagonal scaling</em> with a vector
<img class="math" src="_images/math/badad346f6fbe2e237af99bfbd9a93a4da53a3da.png" alt="d"/>:</p>
<div class="math">
<p><img src="_images/math/61a7d25e3673146402ed26716d6eb60e8e9d18fa.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
W_\mathrm{l} = \diag(d), \qquad
W_\mathrm{l}^{-1} = \diag(d)^{-1}."/></p>
</div><p>This transformation is symmetric:</p>
<div class="math">
<p><img src="_images/math/172415a1aefbbb006e616ac35d880030890ad136.png" alt="W_\mathrm{l}^T = W_\mathrm{l}."/></p>
</div></li>
<li><p>The next <img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/> blocks are positive multiples of <em>hyperbolic
Householder transformations</em>:</p>
<div class="math">
<p><img src="_images/math/0fc13f815b495c77d502992ae392d16844c0950b.png" alt="W_{\mathrm{q},k} = \beta_k ( 2 v_k v_k^T - J), \qquad
W_{\mathrm{q},k}^{-1} = \frac{1}{\beta_k} ( 2 Jv_k v_k^T J - J),
\qquad k = 0,\ldots,M-1,"/></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/8fcff6b5a5c95afb39f5abaedac94b7086911410.png" alt="\beta_k &gt; 0, \qquad v_{k0} &gt; 0, \qquad v_k^T Jv_k = 1, \qquad
J = \left[\begin{array}{cc} 1 &amp; 0 \\ 0 &amp; -I \end{array}\right]."/></p>
</div><p>These transformations are also symmetric:</p>
<div class="math">
<p><img src="_images/math/294ea142766a27b4576f8c3240182c9220174aad.png" alt="W_{\mathrm{q},k}^T = W_{\mathrm{q},k}."/></p>
</div></li>
<li><p>The last <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> blocks are <em>congruence transformations</em> with
nonsingular matrices:</p>
<div class="math">
<p><img src="_images/math/3b0de39a2c386bc0f8d5ee56519cab864e57d389.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k} \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k^T u_{\mathrm{s},k} r_k)}, \qquad
W_{\mathrm{s},k}^{-1} \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k^{-T} u_{\mathrm{s},k} r_k^{-1})}, \qquad
k = 0,\ldots,N-1."/></p>
</div><p>In  general, this operation is not symmetric:</p>
<div class="math">
<p><img src="_images/math/46362a8b56ad9a6cb816f0062260ad22a76b6f08.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k}^T \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k u_{\mathrm{s},k} r_k^T)}, \qquad \qquad
W_{\mathrm{s},k}^{-T} \svec{(u_{\mathrm{s},k})} =
    \svec{(r_k^{-1} u_{\mathrm{s},k} r_k^{-T})}, \qquad \qquad
k = 0,\ldots,N-1."/></p>
</div></li>
</ul>
<p>It is often possible to exploit problem structure to solve
<a class="reference internal" href="#equation-e-conelp-kkt">(1)</a> faster than by standard methods.  The last argument
<code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> of <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> allows the user to
supply a Python  function for solving the KKT equations.  This
function will be called as <code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(W)</span></code>, where <code class="docutils literal notranslate"><span class="pre">W</span></code> is a
dictionary that contains the parameters of the scaling:</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">W['d']</span></code> is the positive vector that defines the diagonal
scaling.   <code class="docutils literal notranslate"><span class="pre">W['di']</span></code> is its componentwise inverse.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">W['beta']</span></code> and <code class="docutils literal notranslate"><span class="pre">W['v']</span></code> are lists of length <img class="math" src="_images/math/4abba779877abb276b98ccb2b4ba9bf2e41947ab.png" alt="M"/>
with the coefficients and vectors that define the hyperbolic
Householder transformations.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">W['r']</span></code> is a list of length <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> with the matrices that
define the the congruence transformations.  <code class="docutils literal notranslate"><span class="pre">W['rti']</span></code> is a
list of length <img class="math" src="_images/math/3bfb3a64189a14b2704f4610827762d5e3145114.png" alt="N"/> with the transposes of the inverses of the
matrices in <code class="docutils literal notranslate"><span class="pre">W['r']</span></code>.</p></li>
</ul>
<p>The function call <code class="docutils literal notranslate"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(W)</span></code> should return a routine for
solving the KKT system <a class="reference internal" href="#equation-e-conelp-kkt">(1)</a> defined by <code class="docutils literal notranslate"><span class="pre">W</span></code>.  It will
be called as <code class="docutils literal notranslate"><span class="pre">f(bx,</span> <span class="pre">by,</span> <span class="pre">bz)</span></code>.  On entry, <code class="docutils literal notranslate"><span class="pre">bx</span></code>, <code class="docutils literal notranslate"><span class="pre">by</span></code>, <code class="docutils literal notranslate"><span class="pre">bz</span></code>
contain the right-hand side.  On exit, they should contain the solution
of the KKT system, with the last component scaled, i.e., on exit,</p>
<div class="math">
<p><img src="_images/math/aaf1e4f8649093b3b1a2a201c97238b5d922ff96.png" alt="b_x := u_x, \qquad b_y := u_y, \qquad b_z := W u_z."/></p>
</div><p>In other words, the function returns the solution of</p>
<div class="math">
<p><img src="_images/math/838e2b03a608af26db2efa9096182aa54d809a3d.png" alt="\left[\begin{array}{ccc}
    P &amp; A^T &amp; G^TW^{-1} \\
    A &amp; 0   &amp; 0  \\
    G &amp; 0   &amp; -W^T
\end{array}\right]
\left[\begin{array}{c}
    \hat u_x \\ \hat u_y \\ \hat u_z
\end{array}\right]
=
\left[\begin{array}{c}
    b_x \\ b_y \\ b_z
\end{array}\right]."/></p>
</div></dd>
<dt><strong>Specifying constraints via Python functions</strong></dt><dd><p>In the default use of <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a>, the linear
constraints and the quadratic term in the objective are parameterized
by CVXOPT matrices <code class="docutils literal notranslate"><span class="pre">G</span></code>, <code class="docutils literal notranslate"><span class="pre">A</span></code>, <code class="docutils literal notranslate"><span class="pre">P</span></code>.  It is possible to specify
these parameters via Python functions that evaluate the corresponding
matrix-vector products and their adjoints.</p>
<ul>
<li><p>If the argument <code class="docutils literal notranslate"><span class="pre">G</span></code> of <code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code> or <code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code> is a
Python function, then
<code class="docutils literal notranslate"><span class="pre">G(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></code>
should evaluate the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/ae4ca00a7da101aa137fa6b84b5467ce39b05349.png" alt="y := \alpha Gx + \beta y \quad
    (\mathrm{trans} = \mathrm{'N'}), \qquad
y := \alpha G^T x + \beta y \quad
    (\mathrm{trans} = \mathrm{'T'})."/></p>
</div></div></blockquote>
</li>
<li><p>Similarly, if the argument <code class="docutils literal notranslate"><span class="pre">A</span></code> is a Python function, then
<code class="docutils literal notranslate"><span class="pre">A(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></code>
should evaluate the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/694498e646bcebcf71487704e8bbabe9b2665425.png" alt="y := \alpha Ax + \beta y \quad
    (\mathrm{trans} = \mathrm{'N'}), \qquad
y := \alpha A^T x + \beta y \quad
    (\mathrm{trans} = \mathrm{'T'})."/></p>
</div></div></blockquote>
</li>
<li><p>If the argument <code class="docutils literal notranslate"><span class="pre">P</span></code> of <code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code> is a Python function, then
<code class="docutils literal notranslate"><span class="pre">P(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0])</span></code>
should evaluate the matrix-vector products</p>
<blockquote>
<div><div class="math">
<p><img src="_images/math/7e65c1c7c403764759e8813348c1b7e2d560f1fa.png" alt="y := \alpha Px + \beta y."/></p>
</div></div></blockquote>
</li>
</ul>
<p>If <code class="docutils literal notranslate"><span class="pre">G</span></code>, <code class="docutils literal notranslate"><span class="pre">A</span></code>, or <code class="docutils literal notranslate"><span class="pre">P</span></code> are Python functions, then the argument
<code class="docutils literal notranslate"><span class="pre">kktsolver</span></code> must also be provided.</p>
</dd>
</dl>
<p>We illustrate these features with three applications.</p>
<p><strong>Example: 1-norm approximation</strong></p>
<blockquote>
<div><p>The optimization problem</p>
<div class="math">
<p><img src="_images/math/b934c490f51b68bde94c85bb2c77c160a78731bc.png" alt="\begin{array}{ll}
\mbox{minimize} &amp; \|Pu-q\|_1
\end{array}"/></p>
</div><p>can be formulated as a linear program</p>
<div class="math">
<p><img src="_images/math/78d5bb409e88f612d4afe2cca2f43186923387e6.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} &amp; \ones^T v \\
\mbox{subject to} &amp; -v \preceq Pu - q  \preceq v.
\end{array}"/></p>
</div><p>By exploiting the structure in the inequalities, the cost of an
iteration of an interior-point method can be reduced to the cost of
least-squares problem of the same dimensions.  (See section 11.8.2 in
the book
<a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex Optimization</a>.)
The code below takes advantage of this fact.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spmatrix</span><span class="p">,</span> <span class="n">mul</span><span class="p">,</span> <span class="n">div</span>

<span class="k">def</span> <span class="nf">l1</span><span class="p">(</span><span class="n">P</span><span class="p">,</span> <span class="n">q</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>

<span class="sd">    Returns the solution u, w of the l1 approximation problem</span>

<span class="sd">        (primal) minimize    ||P*u - q||_1</span>

<span class="sd">        (dual)   maximize    q&#39;*w</span>
<span class="sd">                 subject to  P&#39;*w = 0</span>
<span class="sd">                             ||w||_infty &lt;= 1.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">P</span><span class="o">.</span><span class="n">size</span>

    <span class="c1"># Solve the equivalent LP</span>
    <span class="c1">#</span>
    <span class="c1">#     minimize    [0; 1]&#39; * [u; v]</span>
    <span class="c1">#     subject to  [P, -I; -P, -I] * [u; v] &lt;= [q; -q]</span>
    <span class="c1">#</span>
    <span class="c1">#     maximize    -[q; -q]&#39; * z</span>
    <span class="c1">#     subject to  [P&#39;, -P&#39;]*z  = 0</span>
    <span class="c1">#                 [-I, -I]*z + 1 = 0</span>
    <span class="c1">#                 z &gt;= 0.</span>

    <span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="n">m</span><span class="o">*</span><span class="p">[</span><span class="mf">1.0</span><span class="p">])</span>

    <span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;N&#39;</span><span class="p">):</span>

        <span class="k">if</span> <span class="n">trans</span><span class="o">==</span><span class="s1">&#39;N&#39;</span><span class="p">:</span>
            <span class="c1"># y := alpha * [P, -I; -P, -I] * x + beta*y</span>
            <span class="n">u</span> <span class="o">=</span> <span class="n">P</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>
            <span class="n">y</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span> <span class="o">=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span> <span class="n">u</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span> <span class="o">+</span> <span class="n">beta</span> <span class="o">*</span> <span class="n">y</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span>
            <span class="n">y</span><span class="p">[</span><span class="n">m</span><span class="p">:]</span> <span class="o">=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="o">-</span><span class="n">u</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span> <span class="o">+</span> <span class="n">beta</span> <span class="o">*</span> <span class="n">y</span><span class="p">[</span><span class="n">m</span><span class="p">:]</span>

        <span class="k">else</span><span class="p">:</span>
            <span class="c1"># y := alpha * [P&#39;, -P&#39;; -I, -I] * x + beta*y</span>
            <span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span>  <span class="n">alpha</span> <span class="o">*</span> <span class="n">P</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">m</span><span class="p">:])</span> <span class="o">+</span> <span class="n">beta</span> <span class="o">*</span> <span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>
            <span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="o">-</span><span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="n">m</span><span class="p">:])</span> <span class="o">+</span> <span class="n">beta</span> <span class="o">*</span> <span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span>

    <span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="n">q</span><span class="p">,</span> <span class="o">-</span><span class="n">q</span><span class="p">])</span>
    <span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="mi">2</span><span class="o">*</span><span class="n">m</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span> <span class="p">[]}</span>

    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>

        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns a function f(x, y, z) that solves</span>

<span class="sd">            [ 0  0  P&#39;      -P&#39;      ] [ x[:n] ]   [ bx[:n] ]</span>
<span class="sd">            [ 0  0 -I       -I       ] [ x[n:] ]   [ bx[n:] ]</span>
<span class="sd">            [ P -I -D1^{-1}  0       ] [ z[:m] ] = [ bz[:m] ]</span>
<span class="sd">            [-P -I  0       -D2^{-1} ] [ z[m:] ]   [ bz[m:] ]</span>

<span class="sd">        where D1 = diag(di[:m])^2, D2 = diag(di[m:])^2 and di = W[&#39;di&#39;].</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="c1"># Factor A = 4*P&#39;*D*P where D = d1.*d2 ./(d1+d2) and</span>
        <span class="c1"># d1 = di[:m].^2, d2 = di[m:].^2.</span>

        <span class="n">di</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">]</span>
        <span class="n">d1</span><span class="p">,</span> <span class="n">d2</span> <span class="o">=</span> <span class="n">di</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">di</span><span class="p">[</span><span class="n">m</span><span class="p">:]</span><span class="o">**</span><span class="mi">2</span>
        <span class="n">D</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span><span class="n">d2</span><span class="p">),</span> <span class="n">d1</span><span class="o">+</span><span class="n">d2</span> <span class="p">)</span>
        <span class="n">A</span> <span class="o">=</span> <span class="n">P</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">spmatrix</span><span class="p">(</span><span class="mi">4</span><span class="o">*</span><span class="n">D</span><span class="p">,</span> <span class="nb">range</span><span class="p">(</span><span class="n">m</span><span class="p">),</span> <span class="nb">range</span><span class="p">(</span><span class="n">m</span><span class="p">))</span> <span class="o">*</span> <span class="n">P</span>
        <span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">A</span><span class="p">)</span>

        <span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>

            <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            On entry bx, bz are stored in x, z.  On exit x, z contain the solution,</span>
<span class="sd">            with z scaled: z./di is returned instead of z.</span>
<span class="sd">            &quot;&quot;&quot;</span><span class="s2">&quot;</span>

            <span class="c1"># Solve for x[:n]:</span>
            <span class="c1">#</span>
            <span class="c1">#    A*x[:n] = bx[:n] + P&#39; * ( ((D1-D2)*(D1+D2)^{-1})*bx[n:]</span>
            <span class="c1">#              + (2*D1*D2*(D1+D2)^{-1}) * (bz[:m] - bz[m:]) ).</span>

            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">P</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="p">(</span> <span class="n">mul</span><span class="p">(</span><span class="n">div</span><span class="p">(</span><span class="n">d1</span><span class="o">-</span><span class="n">d2</span><span class="p">,</span> <span class="n">d1</span><span class="o">+</span><span class="n">d2</span><span class="p">),</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span> <span class="o">+</span> <span class="n">mul</span><span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">D</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span><span class="o">-</span><span class="n">z</span><span class="p">[</span><span class="n">m</span><span class="p">:])</span> <span class="p">)</span>
            <span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>

            <span class="c1"># x[n:] := (D1+D2)^{-1} * (bx[n:] - D1*bz[:m] - D2*bz[m:] + (D1-D2)*P*x[:n])</span>

            <span class="n">u</span> <span class="o">=</span> <span class="n">P</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>
            <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span>  <span class="n">div</span><span class="p">(</span><span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">m</span><span class="p">])</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">m</span><span class="p">:])</span> <span class="o">+</span> <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="o">-</span><span class="n">d2</span><span class="p">,</span> <span class="n">u</span><span class="p">),</span> <span class="n">d1</span><span class="o">+</span><span class="n">d2</span><span class="p">)</span>

            <span class="c1"># z[:m] := d1[:m] .* ( P*x[:n] - x[n:] - bz[:m])</span>
            <span class="c1"># z[m:] := d2[m:] .* (-P*x[:n] - x[n:] - bz[m:])</span>

            <span class="n">z</span><span class="p">[:</span><span class="n">m</span><span class="p">]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span><span class="n">di</span><span class="p">[:</span><span class="n">m</span><span class="p">],</span>  <span class="n">u</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[:</span><span class="n">m</span><span class="p">])</span>
            <span class="n">z</span><span class="p">[</span><span class="n">m</span><span class="p">:]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span><span class="n">di</span><span class="p">[</span><span class="n">m</span><span class="p">:],</span> <span class="o">-</span><span class="n">u</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[</span><span class="n">m</span><span class="p">:])</span>

        <span class="k">return</span> <span class="n">f</span>

    <span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">F</span><span class="p">)</span>
    <span class="k">return</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span>  <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;z&#39;</span><span class="p">][</span><span class="n">m</span><span class="p">:]</span> <span class="o">-</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;z&#39;</span><span class="p">][:</span><span class="n">m</span><span class="p">]</span>
</pre></div>
</div>
</div></blockquote>
<p><strong>Example: SDP with diagonal linear term</strong></p>
<blockquote>
<div><p>The SDP</p>
<div class="math">
<p><img src="_images/math/2149e945c5e7e174b2a1146a3669a5a0b1c65f32.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} &amp; \ones^T x \\
\mbox{subject to} &amp; W + \diag(x) \succeq 0
\end{array}"/></p>
</div><p>can be solved efficiently by exploiting properties of the diag
operator.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span>

<span class="k">def</span> <span class="nf">mcsdp</span><span class="p">(</span><span class="n">w</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Returns solution x, z to</span>

<span class="sd">        (primal)  minimize    sum(x)</span>
<span class="sd">                  subject to  w + diag(x) &gt;= 0</span>

<span class="sd">        (dual)    maximize    -tr(w*z)</span>
<span class="sd">                  subject to  diag(z) = 1</span>
<span class="sd">                              z &gt;= 0.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">n</span> <span class="o">=</span> <span class="n">w</span><span class="o">.</span><span class="n">size</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
    <span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;N&#39;</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            y := alpha*(-diag(x)) + beta*y.</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="k">if</span> <span class="n">trans</span><span class="o">==</span><span class="s1">&#39;N&#39;</span><span class="p">:</span>
            <span class="c1"># x is a vector; y is a symmetric matrix in column major order.</span>
            <span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
            <span class="n">y</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">x</span>

        <span class="k">else</span><span class="p">:</span>
            <span class="c1"># x is a symmetric matrix in column major order; y is a vector.</span>
            <span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
            <span class="n">y</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">x</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>


    <span class="k">def</span> <span class="nf">cngrnc</span><span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Congruence transformation</span>

<span class="sd">            x := alpha * r&#39;*x*r.</span>

<span class="sd">        r and x are square matrices.</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="c1"># Scale diagonal of x by 1/2.</span>
        <span class="n">x</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">*=</span> <span class="mf">0.5</span>

        <span class="c1"># a := tril(x)*r</span>
        <span class="n">a</span> <span class="o">=</span> <span class="o">+</span><span class="n">r</span>
        <span class="n">tx</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">trmm</span><span class="p">(</span><span class="n">tx</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">side</span> <span class="o">=</span> <span class="s1">&#39;L&#39;</span><span class="p">)</span>

        <span class="c1"># x := alpha*(a*r&#39; + r*a&#39;)</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">syr2k</span><span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">tx</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;T&#39;</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="n">alpha</span><span class="p">)</span>
        <span class="n">x</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">tx</span><span class="p">[:]</span>

    <span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span> <span class="p">[</span><span class="n">n</span><span class="p">]}</span>

    <span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns a function f(x, y, z) that solves</span>

<span class="sd">                      -diag(z)     = bx</span>
<span class="sd">            -diag(x) - r*r&#39;*z*r*r&#39; = bz</span>

<span class="sd">        where r = W[&#39;r&#39;][0] = W[&#39;rti&#39;][0]^{-T}.</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">rti</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;rti&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>

        <span class="c1"># t = rti*rti&#39; as a nonsymmetric matrix.</span>
        <span class="n">t</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">gemm</span><span class="p">(</span><span class="n">rti</span><span class="p">,</span> <span class="n">rti</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">transB</span> <span class="o">=</span> <span class="s1">&#39;T&#39;</span><span class="p">)</span>

        <span class="c1"># Cholesky factorization of tsq = t.*t.</span>
        <span class="n">tsq</span> <span class="o">=</span> <span class="n">t</span><span class="o">**</span><span class="mi">2</span>
        <span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">tsq</span><span class="p">)</span>

        <span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>
            <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            On entry, x contains bx, y is empty, and z contains bz stored</span>
<span class="sd">            in column major order.</span>
<span class="sd">            On exit, they contain the solution, with z scaled</span>
<span class="sd">            (vec(r&#39;*z*r) is returned instead of z).</span>

<span class="sd">            We first solve</span>

<span class="sd">               ((rti*rti&#39;) .* (rti*rti&#39;)) * x = bx - diag(t*bz*t)</span>

<span class="sd">            and take z = - rti&#39; * (diag(x) + bz) * rti.</span>
<span class="sd">            &quot;&quot;&quot;</span>

            <span class="c1"># tbst := t * bz * t</span>
            <span class="n">tbst</span> <span class="o">=</span> <span class="o">+</span><span class="n">z</span>
            <span class="n">cngrnc</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">tbst</span><span class="p">)</span>

            <span class="c1"># x := x - diag(tbst) = bx - diag(rti*rti&#39; * bz * rti*rti&#39;)</span>
            <span class="n">x</span> <span class="o">-=</span> <span class="n">tbst</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>

            <span class="c1"># x := (t.*t)^{-1} * x = (t.*t)^{-1} * (bx - diag(t*bz*t))</span>
            <span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">tsq</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>

            <span class="c1"># z := z + diag(x) = bz + diag(x)</span>
            <span class="n">z</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span>

            <span class="c1"># z := -vec(rti&#39; * z * rti)</span>
            <span class="c1">#    = -vec(rti&#39; * (diag(x) + bz) * rti</span>
            <span class="n">cngrnc</span><span class="p">(</span><span class="n">rti</span><span class="p">,</span> <span class="n">z</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">)</span>

        <span class="k">return</span> <span class="n">f</span>

    <span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">w</span><span class="p">[:],</span> <span class="n">dims</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">F</span><span class="p">)</span>
    <span class="k">return</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;z&#39;</span><span class="p">]</span>
</pre></div>
</div>
</div></blockquote>
<dl>
<dt><strong>Example: Minimizing 1-norm subject to a 2-norm constraint</strong></dt><dd><p>In the second example, we use a similar trick to solve the problem</p>
<div class="math">
<p><img src="_images/math/6efd575f4ef0199dda05d5b8f4a187112a62224b.png" alt="\begin{array}{ll}
\mbox{minimize}   &amp; \|u\|_1 \\
\mbox{subject to} &amp; \|Au - b\|_2 \leq 1.
\end{array}"/></p>
</div><p>The code below is efficient, if we assume that the number of rows in
<img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/> is greater than or equal to the number of columns.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">qcl1</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Returns the solution u, z of</span>

<span class="sd">        (primal)  minimize    || u ||_1</span>
<span class="sd">                  subject to  || A * u - b ||_2  &lt;= 1</span>

<span class="sd">        (dual)    maximize    b^T z - ||z||_2</span>
<span class="sd">                  subject to  || A&#39;*z ||_inf &lt;= 1.</span>

<span class="sd">    Exploits structure, assuming A is m by n with m &gt;= n.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>

    <span class="c1"># Solve equivalent cone LP with variables x = [u; v].</span>
    <span class="c1">#</span>
    <span class="c1">#     minimize    [0; 1]&#39; * x</span>
    <span class="c1">#     subject to  [ I  -I ] * x &lt;=  [  0 ]   (componentwise)</span>
    <span class="c1">#                 [-I  -I ] * x &lt;=  [  0 ]   (componentwise)</span>
    <span class="c1">#                 [ 0   0 ] * x &lt;=  [  1 ]   (SOC)</span>
    <span class="c1">#                 [-A   0 ]         [ -b ]</span>
    <span class="c1">#</span>
    <span class="c1">#     maximize    -t + b&#39; * w</span>
    <span class="c1">#     subject to  z1 - z2 = A&#39;*w</span>
    <span class="c1">#                 z1 + z2 = 1</span>
    <span class="c1">#                 z1 &gt;= 0,  z2 &gt;=0,  ||w||_2 &lt;= t.</span>

    <span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">1.0</span><span class="p">])</span>
    <span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span> <span class="o">+</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">))</span>
    <span class="n">h</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mf">1.0</span>
    <span class="n">h</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">=</span> <span class="o">-</span><span class="n">b</span>

    <span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s1">&#39;N&#39;</span><span class="p">):</span>
        <span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
        <span class="k">if</span> <span class="n">trans</span><span class="o">==</span><span class="s1">&#39;N&#39;</span><span class="p">:</span>
            <span class="c1"># y += alpha * G * x</span>
            <span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>
            <span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>
            <span class="n">y</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">A</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>

        <span class="k">else</span><span class="p">:</span>
            <span class="c1"># y += alpha * G&#39;*x</span>
            <span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">x</span><span class="p">[</span><span class="o">-</span><span class="n">m</span><span class="p">:])</span>
            <span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>


    <span class="k">def</span> <span class="nf">Fkkt</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns a function f(x, y, z) that solves</span>

<span class="sd">            [ 0   G&#39;   ] [ x ] = [ bx ]</span>
<span class="sd">            [ G  -W&#39;*W ] [ z ]   [ bz ].</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="c1"># First factor</span>
        <span class="c1">#</span>
        <span class="c1">#     S = G&#39; * W**-1 * W**-T * G</span>
        <span class="c1">#       = [0; -A]&#39; * W3^-2 * [0; -A] + 4 * (W1**2 + W2**2)**-1</span>
        <span class="c1">#</span>
        <span class="c1"># where</span>
        <span class="c1">#</span>
        <span class="c1">#     W1 = diag(d1) with d1 = W[&#39;d&#39;][:n] = 1 ./ W[&#39;di&#39;][:n]</span>
        <span class="c1">#     W2 = diag(d2) with d2 = W[&#39;d&#39;][n:] = 1 ./ W[&#39;di&#39;][n:]</span>
        <span class="c1">#     W3 = beta * (2*v*v&#39; - J),  W3^-1 = 1/beta * (2*J*v*v&#39;*J - J)</span>
        <span class="c1">#        with beta = W[&#39;beta&#39;][0], v = W[&#39;v&#39;][0], J = [1, 0; 0, -I].</span>

        <span class="c1"># As = W3^-1 * [ 0 ; -A ] = 1/beta * ( 2*J*v * v&#39; - I ) * [0; A]</span>
        <span class="n">beta</span><span class="p">,</span> <span class="n">v</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;beta&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;v&#39;</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
        <span class="n">As</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">v</span> <span class="o">*</span> <span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">A</span><span class="p">)</span>
        <span class="n">As</span><span class="p">[</span><span class="mi">1</span><span class="p">:,:]</span> <span class="o">*=</span> <span class="o">-</span><span class="mf">1.0</span>
        <span class="n">As</span><span class="p">[</span><span class="mi">1</span><span class="p">:,:]</span> <span class="o">-=</span> <span class="n">A</span>
        <span class="n">As</span> <span class="o">/=</span> <span class="n">beta</span>

        <span class="c1"># S = As&#39;*As + 4 * (W1**2 + W2**2)**-1</span>
        <span class="n">S</span> <span class="o">=</span> <span class="n">As</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">As</span>
        <span class="n">d1</span><span class="p">,</span> <span class="n">d2</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;d&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;d&#39;</span><span class="p">][</span><span class="n">n</span><span class="p">:]</span>
        <span class="n">d</span> <span class="o">=</span> <span class="mf">4.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">**-</span><span class="mi">1</span>
        <span class="n">S</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="n">d</span>
        <span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">S</span><span class="p">)</span>

        <span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>

            <span class="c1"># z := - W**-T * z</span>
            <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="n">div</span><span class="p">(</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span> <span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="n">div</span><span class="p">(</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span> <span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">-=</span> <span class="mf">2.0</span><span class="o">*</span><span class="n">v</span><span class="o">*</span><span class="p">(</span> <span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">blas</span><span class="o">.</span><span class="n">dot</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">1</span><span class="p">:],</span> <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span> <span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">*=</span> <span class="o">-</span><span class="mf">1.0</span>
            <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">/=</span> <span class="n">beta</span>

            <span class="c1"># x := x - G&#39; * W**-1 * z</span>
            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-=</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span> <span class="o">-</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span> <span class="o">+</span> <span class="n">As</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">z</span><span class="p">[</span><span class="o">-</span><span class="p">(</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">):]</span>
            <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span> <span class="o">+</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span>

            <span class="c1"># Solve for x[:n]:</span>
            <span class="c1">#</span>
            <span class="c1">#    S*x[:n] = x[:n] - (W1**2 - W2**2)(W1**2 + W2**2)^-1 * x[n:]</span>

            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">div</span><span class="p">(</span><span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">-</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">),</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>
            <span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>

            <span class="c1"># Solve for x[n:]:</span>
            <span class="c1">#</span>
            <span class="c1">#    (d1**-2 + d2**-2) * x[n:] = x[n:] + (d1**-2 - d2**-2)*x[:n]</span>

            <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">d1</span><span class="o">**-</span><span class="mi">2</span> <span class="o">-</span> <span class="n">d2</span><span class="o">**-</span><span class="mi">2</span><span class="p">,</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span>
            <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:],</span> <span class="n">d1</span><span class="o">**-</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**-</span><span class="mi">2</span><span class="p">)</span>

            <span class="c1"># z := z + W^-T * G*x</span>
            <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span> <span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">As</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>

        <span class="k">return</span> <span class="n">f</span>

    <span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;l&#39;</span><span class="p">:</span> <span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span> <span class="s1">&#39;q&#39;</span><span class="p">:</span> <span class="p">[</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span> <span class="s1">&#39;s&#39;</span><span class="p">:</span> <span class="p">[]}</span>
    <span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">Fkkt</span><span class="p">)</span>
    <span class="k">if</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;status&#39;</span><span class="p">]</span> <span class="o">==</span> <span class="s1">&#39;optimal&#39;</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;x&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span>  <span class="n">sol</span><span class="p">[</span><span class="s1">&#39;z&#39;</span><span class="p">][</span><span class="o">-</span><span class="n">m</span><span class="p">:]</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span>
</pre></div>
</div>
</dd>
<dt><strong>Example: 1-norm regularized least-squares</strong></dt><dd><p>As an example that illustrates how structure can be exploited in
<a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a>, we consider the 1-norm
regularized least-squares problem</p>
<div class="math">
<p><img src="_images/math/e61f71e6c396a94105e3437275d3449a61f9d802.png" alt="\begin{array}{ll}
\mbox{minimize} &amp; \|Ax - y\|_2^2 + \|x\|_1
\end{array}"/></p>
</div><p>with variable <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/>.  The problem is equivalent to the quadratic
program</p>
<div class="math">
<p><img src="_images/math/2ac45fcc15c7339cc8ecbdb592c53bc49bf33c73.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} &amp; \|Ax - y\|_2^2 + \ones^T u \\
\mbox{subject to} &amp; -u \preceq x \preceq u
\end{array}"/></p>
</div><p>with variables <img class="math" src="_images/math/888f7c323ac0341871e867220ae2d76467d74d6e.png" alt="x"/> and <img class="math" src="_images/math/9b444cf6329a14140aee8ff5a06ff30772cc1c2f.png" alt="u"/>.  The implementation below is
efficient when <img class="math" src="_images/math/211284f68205c3e66773eaf026f32a0acdd3dfb3.png" alt="A"/> has many more columns than rows.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">mul</span><span class="p">,</span> <span class="n">div</span><span class="p">,</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">sqrt</span>
<span class="kn">import</span> <span class="nn">math</span>

<span class="k">def</span> <span class="nf">l1regls</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">y</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;</span>

<span class="sd">    Returns the solution of l1-norm regularized least-squares problem</span>

<span class="sd">        minimize || A*x - y ||_2^2  + || x ||_1.</span>

<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
    <span class="n">q</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
    <span class="n">q</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">2.0</span> <span class="o">*</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">y</span>

    <span class="k">def</span> <span class="nf">P</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span> <span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            v := alpha * 2.0 * [ A&#39;*A, 0; 0, 0 ] * u + beta * v</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">v</span> <span class="o">*=</span> <span class="n">beta</span>
        <span class="n">v</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="mf">2.0</span> <span class="o">*</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="p">(</span><span class="n">A</span> <span class="o">*</span> <span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span>


    <span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span><span class="o">=</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span><span class="o">=</span><span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span><span class="o">=</span><span class="s1">&#39;N&#39;</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">            v := alpha*[I, -I; -I, -I] * u + beta * v  (trans = &#39;N&#39; or &#39;T&#39;)</span>
<span class="sd">        &quot;&quot;&quot;</span>

        <span class="n">v</span> <span class="o">*=</span> <span class="n">beta</span>
        <span class="n">v</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span><span class="o">*</span><span class="p">(</span><span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">u</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>
        <span class="n">v</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">alpha</span><span class="o">*</span><span class="p">(</span><span class="o">-</span><span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">u</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>

    <span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>


    <span class="c1"># Customized solver for the KKT system</span>
    <span class="c1">#</span>
    <span class="c1">#     [  2.0*A&#39;*A  0    I      -I     ] [x[:n] ]     [bx[:n] ]</span>
    <span class="c1">#     [  0         0   -I      -I     ] [x[n:] ]  =  [bx[n:] ].</span>
    <span class="c1">#     [  I        -I   -D1^-1   0     ] [zl[:n]]     [bzl[:n]]</span>
    <span class="c1">#     [ -I        -I    0      -D2^-1 ] [zl[n:]]     [bzl[n:]]</span>
    <span class="c1">#</span>
    <span class="c1"># where D1 = W[&#39;di&#39;][:n]**2, D2 = W[&#39;di&#39;][n:]**2.</span>
    <span class="c1">#</span>
    <span class="c1"># We first eliminate zl and x[n:]:</span>
    <span class="c1">#</span>
    <span class="c1">#     ( 2*A&#39;*A + 4*D1*D2*(D1+D2)^-1 ) * x[:n] =</span>
    <span class="c1">#         bx[:n] - (D2-D1)*(D1+D2)^-1 * bx[n:] +</span>
    <span class="c1">#         D1 * ( I + (D2-D1)*(D1+D2)^-1 ) * bzl[:n] -</span>
    <span class="c1">#         D2 * ( I - (D2-D1)*(D1+D2)^-1 ) * bzl[n:]</span>
    <span class="c1">#</span>
    <span class="c1">#     x[n:] = (D1+D2)^-1 * ( bx[n:] - D1*bzl[:n]  - D2*bzl[n:] )</span>
    <span class="c1">#         - (D2-D1)*(D1+D2)^-1 * x[:n]</span>
    <span class="c1">#</span>
    <span class="c1">#     zl[:n] = D1 * ( x[:n] - x[n:] - bzl[:n] )</span>
    <span class="c1">#     zl[n:] = D2 * (-x[:n] - x[n:] - bzl[n:] ).</span>
    <span class="c1">#</span>
    <span class="c1"># The first equation has the form</span>
    <span class="c1">#</span>
    <span class="c1">#     (A&#39;*A + D)*x[:n]  =  rhs</span>
    <span class="c1">#</span>
    <span class="c1"># and is equivalent to</span>
    <span class="c1">#</span>
    <span class="c1">#     [ D    A&#39; ] [ x:n] ]  = [ rhs ]</span>
    <span class="c1">#     [ A   -I  ] [ v    ]    [ 0   ].</span>
    <span class="c1">#</span>
    <span class="c1"># It can be solved as</span>
    <span class="c1">#</span>
    <span class="c1">#     ( A*D^-1*A&#39; + I ) * v = A * D^-1 * rhs</span>
    <span class="c1">#     x[:n] = D^-1 * ( rhs - A&#39;*v ).</span>

    <span class="n">S</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">m</span><span class="p">))</span>
    <span class="n">Asc</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
    <span class="n">v</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">Fkkt</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>

        <span class="c1"># Factor</span>
        <span class="c1">#</span>
        <span class="c1">#     S = A*D^-1*A&#39; + I</span>
        <span class="c1">#</span>
        <span class="c1"># where D = 2*D1*D2*(D1+D2)^-1, D1 = d[:n]**-2, D2 = d[n:]**-2.</span>

        <span class="n">d1</span><span class="p">,</span> <span class="n">d2</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">]</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][</span><span class="n">n</span><span class="p">:]</span><span class="o">**</span><span class="mi">2</span>

        <span class="c1"># ds is square root of diagonal of D</span>
        <span class="n">ds</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">sqrt</span><span class="p">(</span><span class="mf">2.0</span><span class="p">)</span> <span class="o">*</span> <span class="n">div</span><span class="p">(</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][</span><span class="n">n</span><span class="p">:]),</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">d1</span><span class="o">+</span><span class="n">d2</span><span class="p">)</span> <span class="p">)</span>
        <span class="n">d3</span> <span class="o">=</span>  <span class="n">div</span><span class="p">(</span><span class="n">d2</span> <span class="o">-</span> <span class="n">d1</span><span class="p">,</span> <span class="n">d1</span> <span class="o">+</span> <span class="n">d2</span><span class="p">)</span>

        <span class="c1"># Asc = A*diag(d)^-1/2</span>
        <span class="n">Asc</span> <span class="o">=</span> <span class="n">A</span> <span class="o">*</span> <span class="n">spdiag</span><span class="p">(</span><span class="n">ds</span><span class="o">**-</span><span class="mi">1</span><span class="p">)</span>

        <span class="c1"># S = I + A * D^-1 * A&#39;</span>
        <span class="n">blas</span><span class="o">.</span><span class="n">syrk</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
        <span class="n">S</span><span class="p">[::</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="mf">1.0</span>
        <span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">S</span><span class="p">)</span>

        <span class="k">def</span> <span class="nf">g</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>

            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mf">0.5</span> <span class="o">*</span> <span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span> <span class="o">+</span>
                <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+</span> <span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]))</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span>
                <span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]))</span> <span class="p">)</span>
            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">ds</span><span class="p">)</span>

            <span class="c1"># Solve</span>
            <span class="c1">#</span>
            <span class="c1">#     S * v = 0.5 * A * D^-1 * ( bx[:n] -</span>
            <span class="c1">#         (D2-D1)*(D1+D2)^-1 * bx[n:] +</span>
            <span class="c1">#         D1 * ( I + (D2-D1)*(D1+D2)^-1 ) * bzl[:n] -</span>
            <span class="c1">#         D2 * ( I - (D2-D1)*(D1+D2)^-1 ) * bzl[n:] )</span>

            <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
            <span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>

            <span class="c1"># x[:n] = D^-1 * ( rhs - A&#39;*v ).</span>
            <span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">alpha</span><span class="o">=-</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span><span class="o">=</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">trans</span><span class="o">=</span><span class="s1">&#39;T&#39;</span><span class="p">)</span>
            <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">ds</span><span class="p">)</span>

            <span class="c1"># x[n:] = (D1+D2)^-1 * ( bx[n:] - D1*bzl[:n]  - D2*bzl[n:] )</span>
            <span class="c1">#         - (D2-D1)*(D1+D2)^-1 * x[:n]</span>
            <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]),</span> <span class="n">d1</span><span class="o">+</span><span class="n">d2</span> <span class="p">)</span>\
                <span class="o">-</span> <span class="n">mul</span><span class="p">(</span> <span class="n">d3</span><span class="p">,</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="p">)</span>

            <span class="c1"># zl[:n] = D1^1/2 * (  x[:n] - x[n:] - bzl[:n] )</span>
            <span class="c1"># zl[n:] = D2^1/2 * ( -x[:n] - x[n:] - bzl[n:] ).</span>
            <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span>  <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="p">)</span>
            <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s1">&#39;di&#39;</span><span class="p">][</span><span class="n">n</span><span class="p">:],</span> <span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="p">)</span>

        <span class="k">return</span> <span class="n">g</span>

    <span class="k">return</span> <span class="n">solvers</span><span class="o">.</span><span class="n">coneqp</span><span class="p">(</span><span class="n">P</span><span class="p">,</span> <span class="n">q</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">Fkkt</span><span class="p">)[</span><span class="s1">&#39;x&#39;</span><span class="p">][:</span><span class="n">n</span><span class="p">]</span>
</pre></div>
</div>
</dd>
</dl>
</div>
<div class="section" id="optional-solvers">
<span id="s-external"></span><h2>Optional Solvers<a class="headerlink" href="#optional-solvers" title="Permalink to this headline">¶</a></h2>
<p>CVXOPT includes optional interfaces to several other optimization
libraries.</p>
<dl class="simple">
<dt><strong>GLPK</strong></dt><dd><p><a class="reference internal" href="#cvxopt.solvers.lp" title="cvxopt.solvers.lp"><code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span></code></a> with the <code class="docutils literal notranslate"><span class="pre">solver</span></code> option set to
<code class="xref py py-const docutils literal notranslate"><span class="pre">'glpk'</span></code> uses the
simplex algorithm in <a class="reference external" href="http://www.gnu.org/software/glpk/glpk.html">GLPK (GNU Linear Programming Kit)</a>.</p>
</dd>
<dt><strong>MOSEK</strong></dt><dd><p><a class="reference internal" href="#cvxopt.solvers.lp" title="cvxopt.solvers.lp"><code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span></code></a>, <a class="reference internal" href="#cvxopt.solvers.socp" title="cvxopt.solvers.socp"><code class="xref py py-func docutils literal notranslate"><span class="pre">socp</span></code></a>,
and <a class="reference internal" href="#cvxopt.solvers.qp" title="cvxopt.solvers.qp"><code class="xref py py-func docutils literal notranslate"><span class="pre">qp</span></code></a> with the <code class="docutils literal notranslate"><span class="pre">solver</span></code> option
set to <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code> option use <a class="reference external" href="http://www.mosek.com">MOSEK</a>
version 5.</p>
</dd>
<dt><strong>DSDP</strong></dt><dd><p><a class="reference internal" href="#cvxopt.solvers.sdp" title="cvxopt.solvers.sdp"><code class="xref py py-func docutils literal notranslate"><span class="pre">sdp</span></code></a> with the <code class="docutils literal notranslate"><span class="pre">solver</span></code> option set to
<code class="xref py py-const docutils literal notranslate"><span class="pre">'dsdp'</span></code> uses
the <a class="reference external" href="http://www-unix.mcs.anl.gov/DSDP">DSDP5.8</a>.</p>
</dd>
</dl>
<p>GLPK, MOSEK and DSDP are not included in the CVXOPT distribution and
need to be installed separately.</p>
</div>
<div class="section" id="algorithm-parameters">
<span id="s-parameters"></span><h2>Algorithm Parameters<a class="headerlink" href="#algorithm-parameters" title="Permalink to this headline">¶</a></h2>
<p>In this section we list some algorithm control parameters that can be
modified without editing the source code.  These control parameters are
accessible via the dictionary <code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options</span></code>.  By default the
dictionary is empty and the default values of the parameters are
used.</p>
<p>One can change the parameters in the default solvers by
adding entries with the following key values.</p>
<dl class="simple">
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'show_progress'</span></code></dt><dd><p><code class="xref py py-const docutils literal notranslate"><span class="pre">True</span></code> or <code class="xref py py-const docutils literal notranslate"><span class="pre">False</span></code>; turns the output to the screen on or
off (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">True</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'maxiters'</span></code></dt><dd><p>maximum number of iterations (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">100</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'abstol'</span></code></dt><dd><p>absolute accuracy (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-7</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'reltol'</span></code></dt><dd><p>relative accuracy (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-6</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'feastol'</span></code></dt><dd><p>tolerance for feasibility conditions (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-7</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'refinement'</span></code></dt><dd><p>number of iterative refinement steps when solving KKT equations
(default: <code class="xref py py-const docutils literal notranslate"><span class="pre">0</span></code> if the problem has no second-order cone or matrix
inequality constraints; <code class="xref py py-const docutils literal notranslate"><span class="pre">1</span></code> otherwise).</p>
</dd>
</dl>
<p>For example the command</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s1">&#39;show_progress&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span>
</pre></div>
</div>
<p>turns off the screen output during calls to the solvers.</p>
<p>The tolerances <code class="xref py py-const docutils literal notranslate"><span class="pre">'abstol'</span></code>, <code class="xref py py-const docutils literal notranslate"><span class="pre">'reltol'</span></code> and <code class="xref py py-const docutils literal notranslate"><span class="pre">'feastol'</span></code>
have the following meaning.  <a class="reference internal" href="#cvxopt.solvers.conelp" title="cvxopt.solvers.conelp"><code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code></a>
terminates with status <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code> if</p>
<div class="math">
<p><img src="_images/math/54cbbb3d4691d21c5f1604825fce3e264ef4e7cb.png" alt="s \succeq 0, \qquad
\frac{\|Gx + s - h\|_2} {\max\{1,\|h\|_2\}} \leq
    \epsilon_\mathrm{feas}, \qquad
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \leq \epsilon_\mathrm{feas},
    \qquad"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/45bf7a5d17860fe8ca50fd24ff910e00ce5f8a39.png" alt="z \succeq 0, \qquad
\frac{\|G^Tz +  A^Ty + c\|_2}{\max\{1,\|c\|_2\}} \leq
    \epsilon_\mathrm{feas},"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/23507579d8ee310e9bc7a287d88d48f8f5ab891f.png" alt="s^T z \leq \epsilon_\mathrm{abs} \qquad \mbox{or} \qquad
\left( \min\left\{c^Tx,  h^T z + b^Ty \right\} &lt; 0 \quad
    \mbox{and} \quad
\frac{s^Tz} {-\min\{c^Tx, h^Tz + b^T y\}} \leq \epsilon_\mathrm{rel}
\right)."/></p>
</div><p>It returns with status <code class="xref py py-const docutils literal notranslate"><span class="pre">'primal</span> <span class="pre">infeasible'</span></code> if</p>
<div class="math">
<p><img src="_images/math/45ca0c9c05f16b36175b595487b17f411e30a5d6.png" alt="z \succeq 0, \qquad \qquad
\frac{\|G^Tz +A^Ty\|_2}{\max\{1, \|c\|_2\}} \leq
    \epsilon_\mathrm{feas}, \qquad
h^Tz +b^Ty = -1."/></p>
</div><p>It returns with status <code class="xref py py-const docutils literal notranslate"><span class="pre">'dual</span> <span class="pre">infeasible'</span></code> if</p>
<div class="math">
<p><img src="_images/math/b7e4addc1a00973125d6c3b9ba5bd951e6486df5.png" alt="s \succeq 0, \qquad \qquad
\frac{\|Gx+s\|_2}{\max\{1, \|h\|_2\}} \leq \epsilon_\mathrm{feas},
\qquad
\frac{\|Ax\|_2}{\max\{1, \|b\|_2\}} \leq \epsilon_\mathrm{feas},
\qquad c^Tx = -1."/></p>
</div><p>The functions <code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span> <span class="pre">&lt;cvxopt.solvers.lp</span></code>,
<a class="reference internal" href="#cvxopt.solvers.socp" title="cvxopt.solvers.socp"><code class="xref py py-func docutils literal notranslate"><span class="pre">socp</span></code></a> and
<a class="reference internal" href="#cvxopt.solvers.sdp" title="cvxopt.solvers.sdp"><code class="xref py py-func docutils literal notranslate"><span class="pre">sdp</span></code></a> call <code class="xref py py-func docutils literal notranslate"><span class="pre">conelp</span></code>
and hence use the same stopping criteria.</p>
<p>The function <a class="reference internal" href="#cvxopt.solvers.coneqp" title="cvxopt.solvers.coneqp"><code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code></a> terminates with
status <code class="xref py py-const docutils literal notranslate"><span class="pre">'optimal'</span></code> if</p>
<div class="math">
<p><img src="_images/math/c94d8558b73b7597cc60b6a0ec7c758f40c88a8d.png" alt="s \succeq 0, \qquad
\frac{\|Gx + s - h\|_2} {\max\{1,\|h\|_2\}} \leq
    \epsilon_\mathrm{feas}, \qquad
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \leq \epsilon_\mathrm{feas},"/></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/3b8df11e628aac991d176b270cf335fd89834cfc.png" alt="z \succeq 0, \qquad
\frac{\|Px + G^Tz +  A^Ty + q\|_2}{\max\{1,\|q\|_2\}} \leq
    \epsilon_\mathrm{feas},"/></p>
</div><p>and at least one of the following three conditions is satisfied:</p>
<div class="math">
<p><img src="_images/math/36c1c1b5e868253601aefce353956d96322883ae.png" alt="s^T z \leq \epsilon_\mathrm{abs}"/></p>
</div><p>or</p>
<div class="math">
<p><img src="_images/math/5d759a9a1a42876f1cefe2c9fc361df2a167d545.png" alt="\left( \frac{1}{2}x^TPx + q^Tx &lt; 0, \quad
\mbox{and}\quad \frac{s^Tz} {-(1/2)x^TPx - q^Tx} \leq
    \epsilon_\mathrm{rel} \right)"/></p>
</div><p>or</p>
<div class="math">
<p><img src="_images/math/39848b64dc282be81d51d8786746c0b13bd48bcc.png" alt="\left( L(x,y,z) &gt; 0 \quad \mbox{and} \quad \frac{s^Tz}
    {L(x,y,z)} \leq \epsilon_\mathrm{rel} \right)."/></p>
</div><p>Here</p>
<div class="math">
<p><img src="_images/math/fc16f4da2e0dd685363c204baf675d6244c52fbb.png" alt="L(x,y,z) = \frac{1}{2}x^TPx + q^Tx  + z^T (Gx-h) + y^T(Ax-b)."/></p>
</div><p>The function <a class="reference internal" href="#cvxopt.solvers.qp" title="cvxopt.solvers.qp"><code class="xref py py-func docutils literal notranslate"><span class="pre">qp</span></code></a> calls
<code class="xref py py-func docutils literal notranslate"><span class="pre">coneqp</span></code> and hence uses the same
stopping criteria.</p>
<p>The control parameters listed in the GLPK documentation are set
to their default values and can be customized by making an entry
in <code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options['glpk']</span></code>.  The entry must be a
dictionary in which the key/value pairs are GLPK parameter names
and values.  For example, the command</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s1">&#39;glpk&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;msg_lev&#39;</span> <span class="p">:</span> <span class="s1">&#39;GLP_MSG_OFF&#39;</span><span class="p">}</span>
</pre></div>
</div>
<p>turns off the screen output in subsequent
<a class="reference internal" href="#cvxopt.solvers.lp" title="cvxopt.solvers.lp"><code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span></code></a> calls with the <code class="xref py py-const docutils literal notranslate"><span class="pre">'glpk'</span></code> option.</p>
<p>The MOSEK interior-point algorithm parameters are set to their default
values.  They can be modified by adding an entry
<code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options['mosek']</span></code>.  This entry is a dictionary with
MOSEK parameter/value pairs, with the parameter names imported from
<code class="xref py py-mod docutils literal notranslate"><span class="pre">mosek</span></code>.  For details see Section 15 of the MOSEK Python API Manual.</p>
<p>For example, the commands</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">import</span> <span class="nn">mosek</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s1">&#39;mosek&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="n">mosek</span><span class="o">.</span><span class="n">iparam</span><span class="o">.</span><span class="n">log</span><span class="p">:</span> <span class="mi">0</span><span class="p">}</span>
</pre></div>
</div>
<p>turn off the screen output during calls of
<code class="xref py py-func docutils literal notranslate"><span class="pre">lp</span></code> or <code class="xref py py-func docutils literal notranslate"><span class="pre">socp</span></code> with
the <code class="xref py py-const docutils literal notranslate"><span class="pre">'mosek'</span></code> option.</p>
<p>The following control parameters in <code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options['dsdp']</span></code> affect the
execution of the DSDP algorithm:</p>
<dl class="simple">
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'DSDP_Monitor'</span></code></dt><dd><p>the interval (in number of iterations) at which output is printed to
the screen (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">0</span></code>).</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'DSDP_MaxIts'</span></code></dt><dd><p>maximum number of iterations.</p>
</dd>
<dt><code class="xref py py-const docutils literal notranslate"><span class="pre">'DSDP_GapTolerance'</span></code></dt><dd><p>relative accuracy (default: <code class="xref py py-const docutils literal notranslate"><span class="pre">1e-5</span></code>).</p>
</dd>
</dl>
<p>It is also possible to override the options specified in the
dictionary <code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options</span></code> by passing a dictionary with
options as a keyword argument. For example, the commands</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">opts</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;maxiters&#39;</span> <span class="p">:</span> <span class="mi">50</span><span class="p">}</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">options</span> <span class="o">=</span> <span class="n">opts</span><span class="p">)</span>
</pre></div>
</div>
<p>override the options specified in the dictionary
<code class="xref py py-attr docutils literal notranslate"><span class="pre">solvers.options</span></code> and use the options in the dictionary
<code class="xref py py-attr docutils literal notranslate"><span class="pre">opts</span></code> instead. This is useful e.g. when several problem
instances should be solved in parallel, but using different options.</p>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="solvers.html" class="btn btn-neutral float-right" title="Nonlinear Convex Optimization" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="spsolvers.html" class="btn btn-neutral float-left" title="Sparse Linear Equations" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; <a href="copyright.html">Copyright</a> 2004-2020, M.S. Andersen, J. Dahl, L. Vandenberghe
      <span class="lastupdated">
        Last updated on Apr 16, 2020.
      </span>

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
  
    <div class="footer">
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 3.0.1.
    </div>

</body>
</html>